Forming a Critical Tree with Cutwidth k

ZHANG Zhen-kun, YE Xi-qiong

doi:10.13371/j.cnki.chin.q.j.m.2022.04.004

Chinese Quarterly Journal of Mathematics >

2022 , Vol. 37 >Issue 4: 366 - 379

DOI: https://doi.org/10.13371/j.cnki.chin.q.j.m.2022.04.004

Forming a Critical Tree with Cutwidth k

Expand

1. School of Mathematics and Statistics, Huanghuai University, Zhumadian 463000, China;
2. Zhengzhou Electronic Information Engineering College, Zhenzhou 450007, China

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.

Received date: 2022-11-14

Online published: 2022-12-30

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).

Fold

Abstract

The cutwidth of a graph G is the minimum number of overlap edges when G is embedded into a path P_n. 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

Cite this article

ZHANG Zhen-kun, YE Xi-qiong . Forming a Critical Tree with Cutwidth k[J]. Chinese Quarterly Journal of Mathematics, 2022 , 37(4) : 366 -379 . DOI: 10.13371/j.cnki.chin.q.j.m.2022.04.004

Options

Outlines

模态框（Modal）标题

Abstract

Cite this article