Structural Properties of k-Cyclic Cutwidth Critical Graphs with a Centre

Cyclic cutwidth problem is a graph layout problem whose goal is to find an embedding ϕ of the vertices of a graph G with n vertices onto a cycle Cn so as to minimize the maximum cutwidth of graph G. According to the literature, this problem is NP-complete, and some exact results regarding cyclic cutwidth have been reported. For an integer k>1, a graph G with cyclic cutwidth k is k-cyclic cutwidth critical if every proper subgraph of G has cyclic cutwidth less than k and G is homeomorphically minimal. In this paper, from the point of view of graph decomposition, we first characterize decomposable structure of some k-cyclic cutwidth critical graphs. We ascertain that a k-cyclic cutwidth critical graph G with a centre u0 has a subgraph decomposition with either two or three members, and we find that each member is a δ-linear cutwidth critical subgraph of G with δ=k−2 or k−1. The result reveals the structural relation between the cyclic cutwidth and the linear cutwidth of graph G.