4連通圖中最長圈上的可去邊

徐 麗 瓊

(集美大學(xué)理學(xué)院，福建廈門361021)

?

4連通圖中最長圈上的可去邊

徐 麗 瓊

(集美大學(xué)理學(xué)院，福建廈門361021)

摘要：圖的可收縮邊與可去邊是研究連通圖的構(gòu)造和使用歸納法證明連通圖的一些性質(zhì)的有力工具.利用邊點(diǎn)割斷片的性質(zhì)給出了某類4連通圖中在特定子圖上可去邊的分布情況,證明了若4連通圖G的邊點(diǎn)割原子的頂點(diǎn)數(shù)大于2,則G中的最長圈C上至少有3條可去邊.

關(guān)鍵詞：4連通圖;可去邊;邊點(diǎn)割原子

1背景及定義

我們僅考慮有限簡單圖,若無特別說明,有關(guān)圖論的符號和術(shù)語見文獻(xiàn)[1].

圖的可收縮邊與可去邊是研究連通圖的構(gòu)造和使用歸納法證明連通圖的一些性質(zhì)的有力工具.1961年Tutte[2]首先利用3連通圖中存在可收縮邊的性質(zhì)給出了3連通圖的一個(gè)出色的構(gòu)造方法.3連通圖存在可收縮邊的一個(gè)著名的應(yīng)用是由Thomassen[3]在1981年給出.他通過歸納法,用統(tǒng)一的方法簡潔明了地證明了關(guān)于平面圖的3個(gè)著名定理,即1) Kuratowski定理:圖G是可平面的當(dāng)且僅當(dāng)G不含同胚于K5或K3,3的子圖;2) Fary定理:每個(gè)平面圖有平面的線性表示;3) Tutte定理:每個(gè)3連通平面圖有平面的凸表示.在這之前,上述3個(gè)定理的證明都比較繁瑣.

關(guān)于3,4,5連通圖的可去邊的性質(zhì)和分布的一些結(jié)果見文獻(xiàn)[4-11].我們主要研究4連通圖的可去邊,下面先給出k連通圖(k≥3)中可去邊的定義.

設(shè)e是k連通圖G的一條邊,G?e表示圖G做下列運(yùn)算所得的圖:

(i) 從G中去掉e得圖G-e;

(ii) 如果e的某個(gè)端點(diǎn)在G-e中度數(shù)為k-1,則去掉此端點(diǎn),再兩兩聯(lián)結(jié)此端點(diǎn)在G-e中的k-1個(gè)鄰點(diǎn);

(iii) 如果經(jīng)過(ii)中的運(yùn)算后,有重邊出現(xiàn),則用單邊代替它們,使得此圖為簡單圖.

若G?e仍為k連通圖,則稱e為G的可去邊,否則稱e為G的不可去邊.G的所有可去邊的集合記為ER(G),G的所有不可去邊的集合記為EN(G).

定理1[11]設(shè)G是k連通圖(k≥3),|G|≥k+3,則e=xy,e∈EN(G)的充要條件是存在S?V(G),|S|=k-1,使G-e-S恰好有2個(gè)連通分支A和B,其中x∈A,y∈B,且|A|≥2,|B|≥2.

上述定理中,(xy,S)稱為G的一個(gè)分離對,(xy,S;A,B)稱為G的一個(gè)分離分解,A和B稱為G中由(xy,S)分離的邊點(diǎn)割斷片,簡稱為G的邊點(diǎn)割斷片.并稱階最小的邊點(diǎn)割斷片為邊點(diǎn)割原子.如果xy∈E0,則稱A與B為G的E0-邊點(diǎn)割斷片.如果E0-邊點(diǎn)割斷片不包含其他的E0-邊點(diǎn)割斷片作為它的真子集,則稱它為E0-邊點(diǎn)割端片.對S?V(G),A?V(G),S∩A=?,〈S,A〉表示端點(diǎn)分別在S和A中的邊的集合,〈S〉表示端點(diǎn)在S中的邊的集合.

2主要結(jié)果及其證明

下面給出我們的主要定理及其證明.

定理5設(shè)G是階大于6的4連通圖,若G的邊點(diǎn)割原子的頂點(diǎn)數(shù)大于2,則G中的最長圈C上至少有3條可去邊.

證明假設(shè)對G中任一最長圈C,最多只有2條可去邊.由定理4知,|E(C)∩ER(G)|≥2.因此C上恰有2條可去邊.設(shè)E(C)∩ER(G)={e1,e2},記E0=E(C)-{e1,e2}?EN(G).取uw∈E0及G的分離分解(uw,S′;A′,B′),其中u∈A′,w∈B′.此時(shí)有(E(A′)∪〈A′,S′〉)∩{e1,e2}=?或(E(B′)∪〈B′,S′〉)∩{e1,e2}=?或(E(A′)∪〈A′;S′〉)∩{e1,e2}和(E(B′)∪〈B′;S′〉)∩{e1,e2} 都不空.由對稱性,只需考慮下面兩種情況.

情況1(E(A′)∪〈A′,S′〉)∩{e1,e2}=?.

A′為G的E0-邊點(diǎn)割斷片,則A′一定包含一個(gè)E0-邊點(diǎn)割端片,設(shè)A是包含在A′中的E0-邊點(diǎn)割端片,取對應(yīng)的分離分解(xy,S;A,B),其中x∈A,y∈B,S={a,b,c}且xy∈E0.顯然(E(A)∪〈A,S〉)∩{e1,e2}=?.從而存在xz∈E0∩(E(A)∪〈A,S〉),由定理2知z?S.取xz對應(yīng)的分離分解(xz,T;C,D),其中x∈C,z∈D,則有x∈A∩C,z∈A∩D.令

X1=(C∩S)∪(S∩T)∪(T∩A),

X2=(D∩S)∪(S∩T)∪(T∩A),

X3=(D∩S)∪(S∩T)∪(T∩B),

X4=(C∩S)∪(S∩T)∪(T∩B).

由定理2知y∈B∩C.B∩C≠?,則X4是G-xy的點(diǎn)割,故|X4|≥3;同理|X2|≥3,由|X2|+|X4|=6可得|X2|=|X4|=3.因?yàn)閨S|=|T|=3,所以|S∩C|=|A∩T|,|B∩T|=|S∩D|.此時(shí)A∩D={z},否則|A∩D|≥2,則(xz,X2;A∩D,B∪C)是G的分離組,且xz∈E0,易知A∩D是包含在A中的E0-邊點(diǎn)割斷片,且|A∩D|<|A|與A是E0-邊點(diǎn)割端片矛盾.故A∩D={z},由D是G的連通分支且|D|≥3可知D∩S≠?.

情況1.1若|D∩S|=|B∩T|=3,則|X1|=0,從而{y,z}將是G的2-點(diǎn)割,矛盾.

情況1.2若|D∩S|=|B∩T|=2,注意到|X1|≥2,則有|X1|=2,則只有|C∩S|=|A∩T|=1,從而S∩T=?.首先,我們說A∩C={x},否則若|A∩C|≥2,則有X1∪{x}是G的3-點(diǎn)割,矛盾.令A(yù)∩T={a},C∩S=,D∩S={u,v}.ab∈E(G),否則,若ab不屬于E(G),則{x,u,v}是G的3-點(diǎn)割,矛盾.令e′=ab,S′={x}∪{u,v},A′=A-{x},B′=G-e′-S′-A′,則有(e′,S′;A′,B′)是G中的分離分解,其中A′是G的E0-邊點(diǎn)割斷片且 |A′|=2,矛盾.

情況1.3若|D∩S|=|B∩T|=1,則|S∩T|=0,1,或2.

(i) 若|S∩T|=2,則|C∩S|=|A∩T|=0,從而|X1|=2.此時(shí)我們說A∩C={x},否則若|A∩C|≥2,則X1∪{x}是G的3-點(diǎn)割,矛盾.此時(shí)|A|=2,與|A|≥3矛盾.

(ii) 若|S∩T|=1,則|C∩S|=|A∩T|=1,此時(shí)|X3|=3,故B∩D=?.從而|D|=2,矛盾.

(iii) 若|S∩T|=0,則|C∩S|=|A∩T|=2,從而|X3|=2,故B∩D=?.從而|D|=2,矛盾.

情況2(E(A′)∪〈A′;S′〉)∩{e1,e2}和(E(B′)∪〈B′;S′〉)∩{e1,e2} 都不空.

不失一般性,設(shè)e2∈E(A′)∪〈A′,S〉,e1∈E(B′)∪〈B′,S〉.設(shè)A是一個(gè)包含在A′中的E0-邊點(diǎn)割端片,因而存在一個(gè)分離分解(xy,S;A,B),其中x∈A,y∈B,xy∈E0,A?A′.顯然此時(shí)e1∈E(B)∪〈B,S〉.令E1=(E(A)∪〈A,S〉)∩E(C).若 (E(A)∪〈A,S〉)∩E0=?,則E1?ER(G).又e1∈(E(B)∪〈B,S〉)∩E(C)∩ER(G),易見E1∩ER(G)={e2},且e2的一個(gè)端點(diǎn)為x,另一個(gè)端點(diǎn)屬于S.不失一般性,令e2=xa,則a在A-{x}中有鄰點(diǎn),設(shè)為q(否則,{x,b,c}將是G的一個(gè)3-點(diǎn)割,矛盾).由于A是G的連通子圖,故A中必有一條連接頂點(diǎn)x和q的路P.于是可得一個(gè)新的圈C-xa+aq+P,顯然它所含的頂點(diǎn)數(shù)比C多,矛盾.因此(E(A)∪〈A,S〉)∩E0≠?,設(shè)uz∈(E(A)∪〈A,S〉)∩E0,取uz對應(yīng)的一個(gè)分離分解(uz,T;C,D),其中u∈C,z∈D.因此有u∈A∩C,z∈A∩D或z∈S∩D.若x=u由定理3知x∈A∩C,y∈B∩C.類似情況1的討論可得矛盾.現(xiàn)設(shè)x≠u.X1,X2,X3和X4的定義類似情況1.由對稱性不妨設(shè)x∈A∩C或x∈A∩T.由定理2和3,下面可分8種情況討論.

情況2.1x∈A∩C,y∈B∩C,z∈A∩D.

類似情況1的討論可得,|X2|=|X4|=3,|S∩C|=|A∩T|,|B∩T|=|D∩S|≠0,A∩D={z}.

若|D∩S|=|B∩T|=3,類似情況1.1的討論可得矛盾.

若|D∩S|=|B∩T|=2,注意到|X1|≥2,則有|X1|=2,從而|C∩S|=|A∩T|=1,S∩T=?.令A(yù)1=A∩C,S1=X1∪{z},B1=G-A1-S1-xy,(xy,S1;A1,B1) 是G的分離分解,xy∈E0,A1是包含在A中的邊點(diǎn)割斷片,與A是E0-邊點(diǎn)割端片矛盾.

若|D∩S|=|B∩T|=1,則|S∩T|=0,1或2.

(i) 若|S∩T|=2,則|C∩S|=|A∩T|=0,從而|X1|=2.類似情況2.1的討論可得矛盾.

(ii) 若|S∩T|=0或1,類似情況1.3的(ii)和(iii)的討論可得矛盾.

情況2.2x∈A∩C,y∈B∩T,z∈A∩D.

由于A∩D≠?,故X2是G-uz的一個(gè)點(diǎn)割,因此|X2|≥3,所以|T∩A|≥|C∩S|,又|X2|+|X4|=6,所以|X4|≤3,由G是4連通的,可知B∩C=?.如果C∩S=?,則C=A∩C.于是由A∩D≠?知C是包含在A中的E0-邊點(diǎn)割斷片,與A是G中的E0-邊點(diǎn)割端片矛盾.故C∩S≠?,從而T∩A≠?.

若|X1|≥3,則|X3|≤3,B∩D=?,|B|=|B∩T|≤2,矛盾.所以|X1|≤2.又X1∪{y,z}是G的點(diǎn)割,由G的4連通性得|X1|≥2,所以|X1|=2.令A(yù)1=A∩C,S1=X1∪{z},B1=G-xy-A1-S1,則(xy,S1;A1,B1)是G的分離分解且xy∈E0,|A1|<|A|,與A是E0-邊點(diǎn)割端片矛盾.

情況2.3x∈A∩T,y∈B∩C,z∈A∩D.

既然A∩D≠?,|X2|≥3,同理|X4|≥3,又|X2|+|X4|=6,所以有|X2|=|X4|=3,從而|S∩C|=|A∩T|,|B∩T|=|D∩S|,類似情況1的討論,A∩D={z},|X1|≥3,所以|X3|≤3,故B∩D=?.由|D|≥3得|S∩D|≥2.若|S∩D|=3,則|S∩C|=0=|A∩T|,矛盾.所以|S∩D|=2,則|S∩C|≤1,又|S∩C|=|A∩T|≥1,所以|S∩C|=1,從而|S∩T|=0,|A∩T|=1,此時(shí)|X1|=2,矛盾.

情況2.4x∈A∩T,y∈B∩D,z∈A∩D.

根據(jù)對稱性,類似情況2.3的討論可得矛盾.

情況2.5x∈A∩C,y∈B∩C,z∈S∩D.

由B∩C≠?,可得|X4|≥3,從而|X2|≤3,A∩D=?.此時(shí)A∩T≠?,否則A=A∩C,從而|A∩C|≥3.因?yàn)閄1是G-uz-xy的點(diǎn)割,所以|X1|≥2.又D∩S≠?,得|X1|=2.令A(yù)1=A-{u},S1=X1∪{u},B1=G-xy-S1-A1,則G有一分離分解(xy,S1;A1,B1),且A1是包含在A中的E0-邊點(diǎn)割斷片,矛盾.因此A∩T≠?,從而|T∩(B∪S)|≤2.若S∩D={z},則|X3|≤3,因此B∩D=?,從而D={z},矛盾.故|S∩D|≥2及|S∩(C∪T)|≤1,因此有|X4|≤3,又|X4|≥3,所以|X4|=3,此時(shí)|S∩C|=1,|S∩T|=0,|B∩T|=2.這時(shí)|X1|=2.令A(yù)1=A∩C,S1=X1∪{z},B1=G-xy-S1-A1,則G有一分離分解(xy,S1;A1,B1),且A1是包含在A中的E0-邊點(diǎn)割斷片,矛盾.

情況2.6x∈A∩C,y∈B∩T,z∈S∩D.

類似情況2.5的證明可得|X1|≥2.分下面2種情況討論.

(i) |X1|=2.若A∩T≠?,類似情況 2.5的證明可得矛盾.若A∩T=?,由A是連通子圖知,A∩D=?,從而|A∩C|=|A|≥3,令A(yù)1=A-u,S1=X1∪{u},B1=G-xy-S1-A1,則G有一分離分解(xy,S1;A1,B1),且A1是包含在A中的E0-邊點(diǎn)割斷片,矛盾.

(ii) |X1|≥3.則|X3|≤3,從而B∩D=?且|A∩T|≥|S∩D|≥1.又|B∩T|≥1所以|A∩T|≤2.若|A∩T|=2,則|S∩T|=0,|B∩T|=1.若|S∩D|=1,則|X2|=3,A∩D=?,D={z},矛盾.若|S∩D|≥2,則|S∩C|≤1,|X4|≤2,B∩C=?,B={y},矛盾.若|A∩T|=1,則|S∩D|=1,|S∩(C∪T)|=2,若|S∩T|≠0,則|S∩T|=|A∩T|=|B∩T|=1,從而|X2|=3,故A∩D=?,所以D={z},矛盾.若|S∩T|=0,則|X2|=2,從而A∩D=?,D={z},矛盾.

情況2.7x∈A∩T,y∈B∩C,z∈S∩D.

由u∈A∩C,可得|X1|≥3.從而|X3|≤3,B∩D=?.由y∈B∩C,可得|X4|≥3,從而|X2|≤3,A∩D=?.從而|A∩T|≥|S∩D|=|D|≥3.又|S|=|T|=3,所以|S∩C|=|S∩T|=|B∩T|=0,|A∩T|=|S∩D|=3.此時(shí)|X4|=0,矛盾.

情況2.8x∈A∩T,y∈B∩D,z∈S∩D.

由u∈A∩C,y∈B∩D,可得|X3|≥3,|X1|≥3,又 |X1|+|X3|=6,從而|X1|=|X3|=3.類似情況1的討論可得A∩C={u}.若|A∩T|=1,由|A|≥3可得A∩D≠?,從而|X2|≥4,|X4|≤2,故B∩C=?.由|C|=|S∩C|+|A∩C|≥3,可得|S∩C|≥2.又|S|=3,所以|S∩C|=2,|S∩T|=0,|S∩D|=1.此時(shí)|X2|=2,與|X2|≥4矛盾.所以|A∩T|≥2.由C是連通子圖,|C|≥3和|A∩C|=1,可得|S∩C|≥1.又由于|X1|=3,所以 |A∩T|=2,|S∩C|=1,|S∩T|=0.所以|B∩T|=1,|X4|=2,進(jìn)而有B∩C=?,故有|C|=2,矛盾.

故上述定理5成立.

參考文獻(xiàn)：

[1]BONDY J A,MURTY U S A.Graph theory with applications[M].London:Macmillan Press,1976:1-65.

[2]TUTTE W T.A theory of 3-connected graphs[J].Nederl Akad Wet Proc Ser A,1961,64:441-455.

[3]THOMASSEN C.Kuratowski′s theorem[J].J Graph Theo-ry,1981,5:225-241.

[4]HOLTON D,JACKSON B,SAITO A,et al.Removable edges in 3-connected graphs[J].J Graph Theory,1990,14(4):465-473.

[5]蘇健基.3連通圖中可去邊的一些性質(zhì)[J].廣西師范大學(xué)學(xué)報(bào),1996,14(1):12-17.

[6]尹建華.4連通圖的可去邊與4連通圖的構(gòu)造[J].系統(tǒng)科學(xué)與數(shù)學(xué),1999,19(4):434-439.

[7]WU J C,LI X L,SU J J.The number of removable edges in 4-connected graphs[J].J Combin Theory Ser B,2004,92:13-40.

[8]WU J C,LI X L.Removable edges in longest cycles of 4-connected graphs[J].Graphs Combin,2004,20:413-422.

[9]吳吉昌,李學(xué)良.4連通圖中圈上的可去邊和可收縮邊[J].廈門大學(xué)學(xué)報(bào)(自然科學(xué)版),2003,42(5):555-558.

[10]WU J C,LI X L,WANG L S.Removable edges in a cycles of a 4-connected graph[J].Discrete Math,2004,287:103-111.

[11]XU L Q,GUO X F.Removable edges in a 5-connected graph and construction method of 5-connected graphs[J].Discrete Math,2008,308:1726-1731.

[12]XU L Q,GUO X F.Removable edges in a cycle of k-connected graphs[J].Acta Math Sinica：English Series,2011,27(1):1-8.

doi：10.6043/j.issn.0438-0479.201507008

收稿日期：2015-07-03錄用日期：2016-05-04

基金項(xiàng)目：國家自然科學(xué)基金(11301217)；福建省自然科學(xué)基金(2013J01014)；福建省高等學(xué)校新世紀(jì)優(yōu)秀人才(JA14168)

中圖分類號:O 157.5

文獻(xiàn)標(biāo)志碼：A

文章編號：0438-0479(2016)04-0550-04

Removable Edges in the Longest Cycles of a 4-connected Graph

XU Liqiong

(School of Sciences,Jimei University,Xiamen 361021,China)

Abstract:Contractible edges and removable edges in connected graphs are a powerful tool to study the structures of graphs and to prove some properties of connected graphs by induction.In this paper by ananlyzing the properties of edge-vertex cut fragment we show that if an edge-vertex-atom of a 4-connected graph G contains at least three vertices,then there are at least three removable edges in a longest cycle of G.

Key words:4-connected graph;removable edge;edge-vertex cut atom

Email：xuliqiong@jmu.edu.cn

引文格式：徐麗瓊.4連通圖中最長圈上的可去邊[J].廈門大學(xué)學(xué)報(bào)(自然科學(xué)版)，2016,55(4)：550-553.

Citation：XU L Q．Removable edges in the longest cycles of a 4-connected graph[J].Journal of Xiamen University(Natural Science)，2016,55(4)：550-553．(in Chinese)