3连通图的可去边的分布  

DISTRIBUTION OF REMOVABLE EDGES IN 3-CONNECTED GRAPHS

作　　者：欧见平[1] 苏健基[1] 

机构地区：[1]广西师范大学数学系,广西桂林541004

出　　处：《广西师范大学学报（自然科学版）》2001年第1期25-29,共5页Journal of Guangxi Normal University:Natural Science Edition

基　　金：国家自然科学基金资助课题! (1 9561 0 0 1 )

摘　　要：e是 3连通图 G的一条边 ,如果 G-e是某个 3连通图的剖分 ,则称 e是 G的可去边 .研究了 3连通图的可去边的分布规律 ,得到 :1设 C是阶至少为 6的 3连通图 G中的一个圈 ,如果 C上不存在 3个连续的 3度点 ,那么 C上至少有两条可去边 .2设 T是阶至少为 5的 3连通图 G的一棵生成树 ,如果 G中至多存在一个极大半轮 ,那么 T上至少有一条可去边 .由此可得 :阶至少为 5的 3连通 3正则图的生成树上至少有一条可去边 .An edge e of a 3-connected graph G is said to be removable if G-e is the subdivition of a 3-connected graph.The distribution of removable edges in 3-connected graphs is discussed in the paper.The following results are obtained:(1) Let C be a cycle in 3-connected graph G with υ(G)≥6.If this cycle contains no three consecutive vertices with degree three,then there are at least two removable edges in it.(2) Let T be a spanning tree of G with υ(G)≥5.If G contains at most one maximal semiwheel,then T has at least one removable edge,and thus there is at least one removable edge in the spanning tree of 3-connected cubic graphs with order at least five.

关 键 词：3连通图 可去边 圈 生成树 分布规律 简单无向有限图 极大半轮 

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