数学季刊 >

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

DOI: https://doi.org/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
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.

收稿日期: 2022-11-14

  网络出版日期: 2022-12-30

基金资助

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

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

摘要

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.

关键词： Combinatorics; Graph labeling; Cutwidth; Critical tree

本文引用格式

张振坤, 叶稀琼 . K 割宽临界树的构造[J]. 数学季刊, 2022 , 37(4) : 366 -379 . DOI: 10.13371/j.cnki.chin.q.j.m.2022.04.004

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

Options
文章导航

/

〈 〉

版权所有 © 《数学季刊》编辑部
地址：河南省开封市明伦街85号河南大学数学季刊编辑部
电话：0371-23881698　E-mail: sxjk@henu.edu.cn　QQ: 2454327236
本系统由北京玛格泰克科技发展有限公司设计开发　技术支持：support@magtech.com.cn