The cut width of a graph and the value of a vertex separation of an edge graph
Diskretnaya Matematika, Tome 5 (1993) no. 3, pp. 76-80
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)$.
@article{DM_1993_5_3_a5,
author = {P. A. Golovach},
title = {The cut width of a~graph and the value of a~vertex separation of an edge graph},
journal = {Diskretnaya Matematika},
pages = {76--80},
year = {1993},
volume = {5},
number = {3},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/DM_1993_5_3_a5/}
}
P. A. Golovach. The cut width of a graph and the value of a vertex separation of an edge graph. Diskretnaya Matematika, Tome 5 (1993) no. 3, pp. 76-80. http://geodesic.mathdoc.fr/item/DM_1993_5_3_a5/