Geodesic
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.

Voir la notice de l'article provenant de la source Math-Net.Ru

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},
     publisher = {mathdoc},
     volume = {5},
     number = {3},
     year = {1993},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_1993_5_3_a5/}
}
TY  - JOUR
AU  - P. A. Golovach
TI  - The cut width of a~graph and the value of a~vertex separation of an edge graph
JO  - Diskretnaya Matematika
PY  - 1993
SP  - 76
EP  - 80
VL  - 5
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_1993_5_3_a5/
LA  - ru
ID  - DM_1993_5_3_a5
ER  - 
%0 Journal Article
%A P. A. Golovach
%T The cut width of a~graph and the value of a~vertex separation of an edge graph
%J Diskretnaya Matematika
%D 1993
%P 76-80
%V 5
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_1993_5_3_a5/
%G ru
%F 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/