Find in Library

The cutwidth minimization problem consists of finding an arrangement of the vertices of a graph <i>G</i> on a line <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>P</mi><mi>n</mi></msub></semantics></math></inline-formula> with <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>=</mo><mo>|</mo><mi>V</mi><mo>(</mo><mi>G</mi><mo>)</mo><mo>|</mo></mrow></semantics></math></inline-formula> vertices in such a way that the maximum number of overlapping edges (i.e., the congestion) is minimized. A graph <i>G</i> with a cutwidth of <i>k</i> is <i>k</i>-cutwidth critical if every proper subgraph of <i>G</i> has a cutwidth less than <i>k</i> and <i>G</i> is homeomorphically minimal. In this paper, we first verified some structural properties of <i>k</i>-cutwidth critical unicyclic graphs with <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>k</mi><mo>></mo><mn>1</mn></mrow></semantics></math></inline-formula>. We then mainly investigated the critical unicyclic graph set <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi mathvariant="script">T</mi></semantics></math></inline-formula> with a cutwidth of four that contains fifty elements, and obtained a forbidden subgraph characterization of 3-cutwidth unicyclic graphs.