4-连通图中圈上的可去边和可收缩边  

Removable Edges and Contractible Edges in Cycles of 4-Connected Graphs

作　　者：吴吉昌[1] 李学良[2] 

机构地区：[1]西北工业大学计算机科学与工程系,陕西西安710072 [2]南开大学组合数学研究中心,天津300071

出　　处：《厦门大学学报（自然科学版）》2003年第5期555-558,共4页Journal of Xiamen University：Natural Science

摘　　要：给出某些4 连通图中圈上的可收缩边和可去边的分布情况,得到如下结果:最小度至少为4或围长至少为5的4 连通图,其任一圈上至少有两条可去边;对4 连通图中的某些最长圈上至少有两条可收缩边.In this paper we show that in a 4connected graph G with minimum degree at least four or girth at least five, any cycle C of G contains at least two removable edges. Moreover, any longest cycle C of a 4connected graph G contains at least two contractible edges of G whenever the degree of each vertex in C is at least five or there is no 3cycle in the induced subgraphin G.

关 键 词：4-连通图 圈 可去边 可收缩边 最小度 围长 有限简单图 图论 

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