Chinese Quarterly Journal of Mathematics ›› 2022, Vol. 37 ›› Issue (4): 366-379.doi: 10.13371/j.cnki.chin.q.j.m.2022.04.004

Previous Articles     Next Articles

Forming a Critical Tree with Cutwidth k

  

  1. 1. School of Mathematics and Statistics, Huanghuai University, Zhumadian 463000, China;
    2. Zhengzhou Electronic Information Engineering College, Zhenzhou 450007, China
  • Received:2022-11-14 Online:2022-12-30 Published:2022-12-30
  • Contact: ZHANG Zhen-kun (1969-), male, native of Runan, Henan, professor in Huanghuai University, engages in graph theory and combinatorial optimization; E-mail: hhxyzzk@126.com
  • About author:ZHANG Zhen-kun (1969-), male, native of Runan, Henan, professor in Huanghuai University, engages in graph theory and combinatorial optimization; YE Xi-qiong (1975-), female, native of Xinyang, Henan, associate professor of Zhengzhou Electronic Information Engineering College, engages in algebra.
  • Supported by:
    Supported by Soft Science Foundation of Henan Province (Grant No. 192400410212) and the Science and Technology Key Project of Henan Province of China (Grant No. 22210211008).

Abstract: The cutwidth of a graph G is the minimum number of overlap edges when G is embedded into a path Pn. The cutwidth problem for a graph G is to determine the cutwidth of G. A graph G with cutwidth k is k-cutwidth critical if every proper subgraph of G has cutwidth less than k and G is homeomorphically minimal. In this paper, we completely investigated methods of forming a k-cutwidth (k >1) critical tree T.

Key words: Combinatorics, Graph labeling, Cutwidth, Critical tree

CLC Number: