|
The cut width of a graph and the value of a vertex separation of an edge graph
P. A. Golovach
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)$.
Received: 12.07.1991
Citation:
P. A. Golovach, “The cut width of a graph and the value of a vertex separation of an edge graph”, Diskr. Mat., 5:3 (1993), 76–80; Discrete Math. Appl., 3:5 (1993), 517–521
Linking options:
https://www.mathnet.ru/eng/dm692 https://www.mathnet.ru/eng/dm/v5/i3/p76
|
|