4连通图中生成树上的可去边  

Removable Edges in a Spanning Tree of a 4-connected Graph

作　　者：徐丽琼[1] 郭晓峰[1] 

机构地区：[1]厦门大学数学科学学院,福建厦门361005

出　　处：《厦门大学学报（自然科学版）》2007年第1期6-9,共4页Journal of Xiamen University：Natural Science

基　　金：国家自然科学基金(10331020);集美大学科研基金(4411C60652)资助

摘　　要：图的可收缩边与可去边是研究连通图的构造和使用归纳法证明连通图的一些性质的有力工具.利用边点割端片的性质给出某些4连通图中在特定子图上可去边的分布情况,得到了最小度至少为5或围长至少为4的4连通图中在其生成树上存在至少两条可去边;同时也得到了最小度至少为5的4连通图中在其生成树外存在至少两条可去边.Contractible edges and removable edges in connected graphs are a powerful tool to study the structures of connected graphs and to prove some properties of connected graphs by induction. In this paper by ananlyzing the properties of edge-vertex cut end we show that in a 4-connected graph G with minimum degree at least five or girth at least four,there are at least two removable edges in a spanning tree of G; in a 4-connected graph G with minimum degree at least five, there are at least two removable edges out- side a spanning tree of G.

关 键 词：4连通图 可去边 断片 

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