5-连通图最长圈上可收缩边的分布

The Distribution of Contractible Edges of the 5-connected Graphs

图可收缩边的存在性对于研究图的结构和证明图的归纳性质有着重要作用.该文对5-连通图中最长圈可收缩边的分布情况进行研究,证明了若G不包含某些特殊的2-断片,则最长圈C上至少包含六条可收缩边;进一步证明了若最长圈C中没有包含5度点的三边形则C至少包含两条可收缩边.

Contractible edge plays a key role in the research of graphstructure,and in the proof of some graph properties by inductive.In this paper,we focus on the distribution of the contractible edges of some longest cycle of 5-connected graphs.Let C be a longest cycle of 5-connected graph G.Let S =E （C） ∩EN （G）.We show that C contains at least six contractible edges if G is S- 2 - fragment free and no triangle of G[V（C）] contains vertex of degree 5.Further, we show that C contains at least two contractible edges if no triangle of GEV（C）] contains vertex of degree 5.