Abstract:
The cutwidth of a graph and the vertex separation number of a graph are among the graph invariants which are defined by the optimal linear ordering of the vertices. Similar invariants play a part in applied problems in such domains as electronics and programming, and, as a result, are actively investigated.
In this paper we establish some relations between the cutwidth of a graph and the vertex separation number of the line graph. In particular, we prove that if $G$ is a connected graph with more than one edge, all whose vertices are of degree no greater than three, then
$cw(G)=vs(L(G))$, where $L(G)$ is the line graph of the graph $G$, $cw(G)$ is the cutwidth of $G$, and $vs(L(G))$ is the vertex separation number of $L(G)$.