王振剛，齊恩鳳

（山東大學(xué)數(shù)學(xué)學(xué)院，山東 濟(jì)南 250100）

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

王振剛，齊恩鳳

（山東大學(xué)數(shù)學(xué)學(xué)院，山東 濟(jì)南 250100）

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

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

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

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

1 相關(guān)概念

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

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

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

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

2008年，楊朝霞已經(jīng)證明了下述兩個(gè)引理：

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

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

（1）d（xi）≥6；

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

本文將對(duì)楊朝霞的結(jié)果進(jìn)一步改進(jìn)：

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

（1）d（xi）≥6；

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

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

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

假設(shè)A∩C≠?。此時(shí)X1是G的一個(gè)點(diǎn)割。此時(shí)必有｜X1｜≥6成立，否則，有｜X1｜＝5成立。既然uv1∈E0∩E（［X1］），則X1是G的E0-點(diǎn)割，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≠?。此時(shí)又分以下幾種情況：

（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。此時(shí)｜X2｜＝5，則A∩D＝?，否則A∩D是G-X2的E0-斷片（或E0-斷片的和），與A是E0-端片矛盾。｜D｜＝｜S∩D｜＝1，設(shè)D＝｛t1｝，則t1uv1t1是G的3-圈。根據(jù)引理1，t1∈V（P），d（t1）＝5，矛盾。

若｜S∩T｜＝1，則｜A∩T｜＝3，｜X1｜≥6，則｜S∩C｜≥2。既然｜S｜＝5，又因?yàn)镈∩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，設(shè)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，設(shè)D＝S∩D＝｛t3｝，d（t3）＝5，且t3uv1t3是3-圈，矛盾。

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

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

由此可知，A∩C＝?。

由對(duì)稱性，A∩D＝?＝A∩C。此時(shí)A＝A∩T≠?。A中不能只含有一個(gè)元素，否則有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＝?。由對(duì)稱性不妨設(shè)B∩D＝?，則B＝B∩C≠?，｜X4｜≥5，｜S｜＝5，故｜X4｜＝5。此時(shí)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的對(duì)稱性，只需討論｜S∩C｜＝2或1，

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

若｜S∩C｜＝1，則｜X4｜＝3，所以B∩C＝?，又因?yàn)锳∩C＝?，所以｜C｜＝｜S∩C｜＝1，設(shè)C＝S∩C＝｛t6｝，d（t6）＝5，且t6v1ut6是3-圈，矛盾。

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

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

（1）d（xi）≥6；

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

證明：設(shè)x′y′是圈C上的一條邊，顯然P＝C－x′y′是G中一條最長（x′，y′）-路。由引理3可知，P至少包含兩條可收縮邊，設(shè)為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］.山東大學(xué)學(xué)報(bào)：理學(xué)版，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－），男，碩士研究生，研究方向?yàn)閳D論。Email：zhengangok＠qq.com