5-連通圖的可收縮邊的分布

王振剛，齊恩鳳

（山東大學數學學院，山東 濟南 250100）

5-連通圖的可收縮邊的分布

王振剛，齊恩鳳

（山東大學數學學院，山東 濟南 250100）

圖的可收縮邊問題對于研究圖的結構和證明圖的某些性質有著重要作用。本文給出了5-連通圖中某些最長圈可收縮邊的分布情況，用樹型結構理論進行分類討論，得到如下結論：不含2-斷片的5-連通圖的最長圈上至少有三條可收縮邊。

5-連通；可收縮邊；最長圈

近年來，連通圖中的可收縮邊的存在性和分布情況成為人們十分關注的課題［1］。Tutte［2］利用3-連通圖的可收縮邊給出了3-連通圖的結構特征，并證明了每一個階數至少為5的3-連通圖都含有可收縮邊。Thomassen［3］利用3-連通圖可收縮邊的存在性，通過歸納法給出了Kuratowski定理一個簡潔的證明。更多的關于可收縮邊的結果由Krisell［4］給出。由此可以看出，一個圖的可收縮邊是探討圖的結構、利用歸納法證明圖的某些性質的有力工具。

本文進一步考慮某些5-連通圖上最長圈上可收縮邊的情況，改進了楊朝霞［5］的結果，得到如下結論：不含2-斷片的5-連通圖的最長圈上至少有3條可收縮邊。

1 相關概念

本文考慮的都是有限簡單圖，所討論的5-連通圖G都是連通度k（G）＝5的圖。

V（G）和E（G）分別表示G的頂點集和邊集。設e＝xy∈E（G），我們將頂點x，y去掉，并將與這兩個頂點相關聯的邊去掉，然后增加一個新頂點，將新頂點與原頂點x，y相鄰接的頂點鄰接，如此我們叫做把邊e收縮，記為G／e。如果收縮e后，G仍是5-連通的，則e是G的可收縮邊。如果去掉G中一個5個點的點集T后，G不連通，則稱T為G的5-點割。顯然，若e是G的不可收縮邊，則G中存在一個包含e的兩個端點的5-點割。G的所有可收縮邊記為EC（G）。

設A，B?V（G），A∩B＝?，A≠?≠B，定義＜A，B＞＝｛xy∈E（G）：x∈A，y∈B｝。用N表示V（G）的非空子集，則N在G中的導出子圖用［N］表示。G中兩點x與y之間的路記為（x，y）-路。若e＝xy∈E（G），且xy?EC（G），則易知G中存在包含x與y的5-點割T，我們稱G-T的各個連通分支為斷片。設E0?E（G）－EC（G），若xy∈E0，設T是包含x，y，的5-點割，則稱T為E0-點割，稱G-T的各個連通分支為E0-斷片。如果E0-斷片不包含其他E0-斷片作為它的真子集，則稱它為E0-端片。特別地，若A是一個斷片，且｜A｜＝2，則稱A為2-斷片。

2 5-連通圖的最長圈上可收縮邊的分布情況

2008年，楊朝霞已經證明了下述兩個引理：

引理1［5］設P：x＝x1x2…xn是5-連通圖G的一條最長（x，y）-路。若xixi＋1是一條不可收縮邊，且S＝｛xi，xi＋1，u1，u2，u3｝是其相應的5-點割，則G-S的每一個斷片至少包含P上的一個點。

引理2［5］設G是5-連通圖且不包含2-斷片。P：x＝x1x2…xn＝y是G的一條最長（x，y）-路。若路P上任一頂點xi都滿足以下兩個條件之一，則P至少包含一條可收縮邊：

（1）d（xi）≥6；

（2）若d（xi）＝5，則［V（P）］中無3-圈包含它。

本文將對楊朝霞的結果進一步改進：

引理3設G是5-連通圖且G不包含2-斷片。P：x＝x1x2…xn＝y是G的一條最長（x，y）-路。若路P上任一頂點xi都滿足以下兩個條件之一，則P至少包含兩條可收縮邊：

（1）d（xi）≥6；

（2）d（xi）＝5，則［V（P）］中無3-圈包含它。

證明：反證法。根據引理2，假設P上只有一條可收縮邊，不妨設為xjxj＋1。設E0＝E（P）－xjxj＋1，則對于每一條邊xixi＋1（i≠j），都有相應的E0-點割S＝｛xi，xi＋1，u1，u2，u3｝的導出子圖［S］包含它，且對于G-S的每一個連通分支都是E0-斷片。設S′是G的一個E0-點割，A′是G-S′的一個E0-斷片，B′＝G－A′－S′是其他E0-斷片之和。顯然xjxj＋1∈［V（A′）∪S′］或［V（B′）∪S′］。不失一般性，我們可設xjxj＋1∈［V（B′）∪S′］，則xjxj＋1?［V（A′）∪S′］。既然每一個E0-斷片都包含一個E0-端片作為它的子集，我們可設A是A′的一個E0-端片，且B＝G－A－S是其他E0-斷片之和。既然A是A′的子集，顯然，xjxj＋1?［V（A）∪S］。由引理1可知E（P）∩＜A，S＞≠?，設v1u∈E（P）∩＜A，S＞，其中v1∈A，u∈S。既然v1u∈E0是不可收縮邊，設其對應的E0-點割為T＝｛u，v1，w，s，t｝，令G-T＝C∪D，其中C≠?≠D。易知u∈S∩T，v1∈A∩T。設

首先，我們證明A∩C＝?。

假設A∩C≠?。此時X1是G的一個點割。此時必有｜X1｜≥6成立，否則，有｜X1｜＝5成立。既然uv1∈E0∩E（［X1］），則X1是G的E0-點割，A∩C是G-X1的E0-斷片（或E0-斷片的和），與A是G的E0-端片相矛盾。故｜X1｜≥6。注意到｜S｜＋｜T｜＝｜X1｜＋｜X3｜＝10，故｜X3｜≤4，由G是5-連通圖可知B∩D＝?。我們說D∩S≠?，否則，有D＝D∩A，則D是包含在A中的E0-斷片，與A是G的E0-端片相矛盾。故D∩S≠?。此時又分以下幾種情況：

（1）如果B∩T≠?，｜X3｜≤4，則｜B∩T｜＝1或2，

（1.1）若｜B∩T｜＝1，則｜S∩T｜＝1或2。

若｜S∩T｜＝2，則｜A∩T｜＝2，｜S∩D｜＝1，｜S∩C｜＝2。此時｜X2｜＝5，則A∩D＝?，否則A∩D是G-X2的E0-斷片（或E0-斷片的和），與A是E0-端片矛盾。｜D｜＝｜S∩D｜＝1，設D＝｛t1｝，則t1uv1t1是G的3-圈。根據引理1，t1∈V（P），d（t1）＝5，矛盾。

若｜S∩T｜＝1，則｜A∩T｜＝3，｜X1｜≥6，則｜S∩C｜≥2。既然｜S｜＝5，又因為D∩S≠?，｜S∩T｜＝1，所以｜S∩C｜＝2或3，

若｜S∩C｜＝2，｜S∩D｜＝2，則｜X3｜＝｜X4｜＝4，故B∩C＝?＝B∩D，所以｜B｜＝｜B∩T｜＝1，設B＝B∩T＝｛t2｝，d（t2）＝5，且t2xixi＋1t2是3-圈，矛盾。

若｜S∩C｜＝3，｜S∩D｜＝1，則｜X2｜＝5，由A是E0-端片可知，A∩D＝?。故｜D｜＝｜S∩D｜＝1，設D＝S∩D＝｛t3｝，d（t3）＝5，且t3uv1t3是3-圈，矛盾。

（1.2）若｜B∩T｜＝2，D∩S≠?，則｜S∩T｜＝1。此時｜A∩T｜＝2，｜S∩D｜＝1，則｜X2｜＝4，A∩D＝?，得｜D｜＝｜S∩D｜＝1，設D＝S∩D＝｛t4｝，d（t4）＝5，且t4uv1t4是3-圈，矛盾。

（2）如果B∩T＝?，則B＝B∩C≠?，｜X4｜≥5，｜S｜＝5，所以S∩D＝?，矛盾。

由此可知，A∩C＝?。

由對稱性，A∩D＝?＝A∩C。此時A＝A∩T≠?。A中不能只含有一個元素，否則有3-圈包含它，又因G無2-斷片，故｜A｜＝｜A∩T｜≥3。又u∈S∩T，故｜B∩T｜＝0或1。

若｜B∩T｜＝0。u∈S∩T，｜S∩T｜≥1，由｜S｜＝｜T｜＝5可知，總有｜X3｜≤4或｜X4｜≤4成立，故B∩C＝?或B∩D＝?。由對稱性不妨設B∩D＝?，則B＝B∩C≠?，｜X4｜≥5，｜S｜＝5，故｜X4｜＝5。此時D∩S＝?，又B∩D＝?，故D＝?，矛盾。

若｜B∩T｜＝1。由｜T｜＝5，｜A∩T｜≥3，u∈S∩T，則｜S∩T｜＝1，又｜S｜＝5，由S∩C和S∩D的對稱性，只需討論｜S∩C｜＝2或1，

若｜S∩C｜＝2，則｜S∩D｜＝2，所以｜X3｜＝｜X4｜＝4，故B∩C＝?＝B∩D，所以｜B｜＝｜B∩T｜＝1，設B＝B∩T＝｛t5｝，d（t5）＝5，且t5xixi＋1t5是3-圈，矛盾。

若｜S∩C｜＝1，則｜X4｜＝3，所以B∩C＝?，又因為A∩C＝?，所以｜C｜＝｜S∩C｜＝1，設C＝S∩C＝｛t6｝，d（t6）＝5，且t6v1ut6是3-圈，矛盾。

根據以上討論可知P至少包含兩條可收縮邊，即原命題成立。證畢。

定理1 設G是5-連通圖且G不包含2-斷片。C：x＝x1x2…xn＝y是G的任意最長圈。若圈C上任一頂點xi都滿足以下條件之一，則C至少包含三條可收縮邊：

（1）d（xi）≥6；

（2）d（xi）＝5，則［V（C）］中無3-圈包含它。

證明：設x′y′是圈C上的一條邊，顯然P＝C－x′y′是G中一條最長（x′，y′）-路。由引理3可知，P至少包含兩條可收縮邊，設為u1v1和u2v2，則P′＝C－u1v1是G中一條最長（u1，v1）-路，由引理3可知，P′包含兩條可收縮邊，至少有一條u3v3≠u2v2，故C上至少有三條可收縮邊。證畢。

［1］BONDY JA，MURTY U SR.Graph theory with applications［M］.London：The Macmillan Press Ltd，1976.

［2］TUTTEW T.A theory of 3-connected graphs［J］.Indag Math，1961，23：441－455.

［3］THOMASSEN C. Planarity and duality of finite and infinite graphs［J］.J Combin Theory Ser B，1980，29（2）：244－271.

［4］KRISELL M. A survey on contractible edges in graph of a prescribed vertex connectivity［J］.Graphs and Combinatorics，2002，18（1）：1－30.

［5］楊朝霞.某些5-連通圖中最長圈上的可收縮邊［J］.山東大學學報：理學版，2008，43（6）：12－14.

Distribution of contractible edges of some 5-connected graphs

WANG Zhen-gang，QI En-feng
（School of Mathematics，Shandong University，Jinan 250100，China））

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 contrac tible edges in some longest cycles of 5-connec tedg raphs and address their classification with tree struc ture theory．Our conclusion is that at least three contrac tible edges exist on some longest cycles of 5-connec tedg raphs．

5-connected；contrac tible edge；the longest cycle

O157.5

A

1002-4026（2014）05-0103-03

10.3976／j.issn.1002－4026.2014.05.019

2014-06-01

王振剛（1989－），男，碩士研究生，研究方向為圖論。Email：zhengangok＠qq.com