Decomposability of a class of k-cutwidth critical graphs
2021
The cutwidth minimization problem consists of finding an arrangement of the vertices of a graph G on a line $$P_n$$
with $$n=|V(G)|$$
vertices, in such a way that the maximum number of overlapping edges (i.e., the congestion) is minimized. A graph G with cutwidth k is k-cutwidth critical if every proper subgraph of G has cutwidth less than k and G is homeomorphically minimal. In this paper, we mainly investigated a class of decomposable k-cutwidth critical graphs for $$k\ge 2$$
, which can be decomposed into three $$(k-1)$$
-cutwidth critical subgraphs.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
14
References
0
Citations
NaN
KQI