4-连通平面图中的圈

Cycles in 4-connected planar graphs

主要讨论4-连通平面图中的圈的问题,令G为n个顶点的4-连通平面图.Tutte等许多学者[1-6]给出了:G中含有长为k的圈,其中对任意的k∈{n,n-1,n-2,n-3},k≥3都成立.文[7]中证明了如下结论:G中含有长为k的圈,其中对任意的k∈{n-4,n-5,n-6},k≥3都成立.在其基础上运用讨论可收缩边的方法证明了G中含有长为n-7(n≥9)的圈.从而推广了文献[7]中的给出的结果.

The problem of cycles of 4 - connected planar graph is considered. Let G be a 4 - connected planar graph on n vertices. Tutte and many other scholars^[1-6] show that G contains a cycle of length k for each k ∈ { n,n -1,n-2,n-3} withk≥3. It proves that Gcontainsacycleoflengthkforeachk∈{n,n-1,n-2,n-3t with k≥3 in [7]. By discussing contractible edges we get that there is a cycle of length n -7（n≥9） in G,which generalized the results of [ 7 ].