Structures of Critical Nontree Graphs with Cutwidth Four

The cutwidth of a graph G is the smallest integer k (k = 1) such that the vertices of G are arranged in a linear layout [v(1), v(2), ... , v(n)], in such a way that for each i = 1, 2, ... , n -1, there are at most k edges with one endpoint in {v(1), v(2), ... , v(i)} and the other in {v(i+1), ... , v(n)}. The cutwidth problem for G is to determine the cutwidth k of G. A graph G with cutwidth k is k-cutwidth critical if every proper subgraph of G has a cutwidth less than k and G is homeomorphically minimal. In this paper, except five irregular graphs, other 4-cutwidth critical graphs were resonably classified into two classes, which are graph class with a central vertex v(0), and graph class with a central cycle C-q of length q = 6, respectively, and any member of two graph classes can skillfuly achieve a subgraph decomposition S with cardinality 2, 3 or 4, where each member of S is either a 2-cutwith graph or a 3-cutwidth graph.

Automated summary

The cutwidth of a graph G is the smallest integer k such that the vertices can be arranged in a linear layout with at most k edges crossing between consecutive vertices. The cutwidth problem is to determine this value for a given graph. A graph with cutwidth k is k-cutwidth critical if every proper subgraph has a cutwidth less than k and the graph is homeomorphically minimal. In this paper, 4-cutwidth critical graphs, except for five irregular ones, are classified into two classes: those with a central vertex and those with a central cycle of length six. Both classes can be decomposed into subgraphs with cardinality 2, 3, or 4, where each subgraph is either a 2-cutwidth or a 3-cutwidth graph.