Structures of Critical Nontree Graphs with Cutwidth Four

Zhenkun Zhang () and Hongjian Lai
Additional contact information
Zhenkun Zhang: School of Mathematics and Statistics, Huanghuai University, Zhumadian 463000, China
Hongjian Lai: Department of Mathematics, West Virginia University, Morgantown, WV 26506, USA

Mathematics, 2023, vol. 11, issue 7, 1-22

Abstract: 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.

Keywords: graph labeling; cutwidth; critical graph; graph decomposition (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/7/1631/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/7/1631/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:7:p:1631-:d:1109398

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().