AppliedMath (Nov 2022)

On Critical Unicyclic Graphs with Cutwidth Four

  • Zhenkun Zhang,
  • Hongjian Lai

DOI
https://doi.org/10.3390/appliedmath2040036
Journal volume & issue
Vol. 2, no. 4
pp. 621 – 637

Abstract

Read online

The cutwidth minimization problem consists of finding an arrangement of the vertices of a graph G on a line Pn 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 a cutwidth of 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, we first verified some structural properties of k-cutwidth critical unicyclic graphs with k>1. We then mainly investigated the critical unicyclic graph set T with a cutwidth of four that contains fifty elements, and obtained a forbidden subgraph characterization of 3-cutwidth unicyclic graphs.

Keywords