5-连通图的可收缩边的分布

Distribution of contractible edges of some 5-connected graphs

图的可收缩边问题对于研究图的结构和证明图的某些性质有着重要作用。本文给出了5-连通图中某些最长圈可收缩边的分布情况,用树型结构理论进行分类讨论,得到如下结论:不含2-断片的5-连通图的最长圈上至少有三条可收缩边。

Contractible edge issue plays an important role in the research on graph structure and the proof of some graph properties. We present the distribution of the contractible edges in some longest cycles of 5-connected graphs and address their classification with tree structure theory. Our conclusion is that at least three contractible edges exist on some longest cycles of .5-connected graphs.