3连通图的可去边的分布

DISTRIBUTION OF REMOVABLE EDGES IN 3-CONNECTED GRAPHS

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.