K 割宽临界树的构造

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

数学季刊 ›› 2022, Vol. 37 ›› Issue (4): 366-379.doi: 10.13371/j.cnki.chin.q.j.m.2022.04.004

K 割宽临界树的构造

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

收稿日期:2022-11-14 出版日期:2022-12-30 发布日期:2022-12-30
通讯作者: 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
作者简介: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 Soft Science Foundation of Henan Province (Grant No. 192400410212) and the Science and Technology Key Project of Henan Province of China (Grant No. 22210211008).

Forming a Critical Tree with Cutwidth k

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

关键词: Combinatorics, Graph labeling, Cutwidth, Critical tree

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

中图分类号:

O157.6
O221

张振坤, 叶稀琼. K 割宽临界树的构造[J]. 数学季刊, 2022, 37(4): 366-379.

ZHANG Zhen-kun, YE Xi-qiong. Forming a Critical Tree with Cutwidth k[J]. Chinese Quarterly Journal of Mathematics, 2022, 37(4): 366-379.

[1]	林艺舒, 常彩冰, 刘岩. 图族和树族的带宽和割宽的遍历性[J]. 数学季刊, 2022, 37(4): 355-365.
[2]	任云霞, 王世英. 局部扭立方的1好邻连通度和诊断度[J]. 数学季刊, 2017, 32(4): 371-381.
[3]	张振坤, 余敏. 分裂图的区间图完全化问题[J]. 数学季刊, 2015, 30(2): 308-316.
[4]	郝建修, 李湘露. L_∞模下的二维带宽问题[J]. 数学季刊, 2004, 19(4): 362-367.

K 割宽临界树的构造

Forming a Critical Tree with Cutwidth k

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

编辑推荐

Metrics

本文评价