k-割宽图的一个结构性质  

STRUCTURAL PROPERTY OF K-CUTWIDTH GRAPH

作　　者：张振坤[1] 叶希琼 庞留勇[1] ZHANG Zhen-kun;YE Xi-qiong;PANG Liu-yong(Huanghuai University,Zhumadian 463000,China;Zhengzhou Electronic Information Engineering College,Zhengzhou 450007,China)

机构地区：[1]黄淮学院,河南驻马店463000 [2]郑州电子信息工程学校,河南郑州450007

出　　处：《南阳理工学院学报》2021年第4期123-128,共6页Journal of Nanyang Institute of Technology

基　　金：河南省软科学研究计划项目(192400410212);河南省科技攻关项目(212102310464)。

摘　　要：在图的最优嵌入问题中,图的割宽计算是其中较为著名的一个NP-困难问题。本文刻画了k-割宽图的一个结构,并将k-割宽无圈图的一个结构推广到了一般的k-割宽图类。For the optimal embedding problems on graphs,one of the famous NP-hard problems is to compute the cutwidth of graph.In this paper,a general structural property on k-cutwidth graphs was established for integer k>1.Based on this,the structure of some k-cutwidth acyclic graphs was generalized to the general k-cutwidth graphs.

关 键 词：图 图标号 割宽 结构 

分 类 号：O157.5[理学—数学]