4连通图中最长圈上的可去边

徐 丽 琼

(集美大学理学院，福建厦门361021)



4连通图中最长圈上的可去边

徐 丽 琼

(集美大学理学院，福建厦门361021)

摘要：图的可收缩边与可去边是研究连通图的构造和使用归纳法证明连通图的一些性质的有力工具.利用边点割断片的性质给出了某类4连通图中在特定子图上可去边的分布情况,证明了若4连通图G的边点割原子的顶点数大于2,则G中的最长圈C上至少有3条可去边.

关键词：4连通图;可去边;边点割原子

1背景及定义

我们仅考虑有限简单图,若无特别说明,有关图论的符号和术语见文献[1].

图的可收缩边与可去边是研究连通图的构造和使用归纳法证明连通图的一些性质的有力工具.1961年Tutte[2]首先利用3连通图中存在可收缩边的性质给出了3连通图的一个出色的构造方法.3连通图存在可收缩边的一个著名的应用是由Thomassen[3]在1981年给出.他通过归纳法,用统一的方法简洁明了地证明了关于平面图的3个著名定理,即1) Kuratowski定理:图G是可平面的当且仅当G不含同胚于K5或K3,3的子图;2) Fary定理:每个平面图有平面的线性表示;3) Tutte定理:每个3连通平面图有平面的凸表示.在这之前,上述3个定理的证明都比较繁琐.

关于3,4,5连通图的可去边的性质和分布的一些结果见文献[4-11].我们主要研究4连通图的可去边,下面先给出k连通图(k≥3)中可去边的定义.

设e是k连通图G的一条边,G⊖e表示图G做下列运算所得的图:

(i) 从G中去掉e得图G-e;

(ii) 如果e的某个端点在G-e中度数为k-1,则去掉此端点,再两两联结此端点在G-e中的k-1个邻点;

(iii) 如果经过(ii)中的运算后,有重边出现,则用单边代替它们,使得此图为简单图.

若G⊖e仍为k连通图,则称e为G的可去边,否则称e为G的不可去边.G的所有可去边的集合记为ER(G),G的所有不可去边的集合记为EN(G).

定理1[11]设G是k连通图(k≥3),|G|≥k+3,则e=xy,e∈EN(G)的充要条件是存在S⊂V(G),|S|=k-1,使G-e-S恰好有2个连通分支A和B,其中x∈A,y∈B,且|A|≥2,|B|≥2.

上述定理中,(xy,S)称为G的一个分离对,(xy,S;A,B)称为G的一个分离分解,A和B称为G中由(xy,S)分离的边点割断片,简称为G的边点割断片.并称阶最小的边点割断片为边点割原子.如果xy∈E0,则称A与B为G的E0-边点割断片.如果E0-边点割断片不包含其他的E0-边点割断片作为它的真子集,则称它为E0-边点割端片.对S⊂V(G),A⊂V(G),S∩A=ø,〈S,A〉表示端点分别在S和A中的边的集合,〈S〉表示端点在S中的边的集合.

2主要结果及其证明

下面给出我们的主要定理及其证明.

定理5设G是阶大于6的4连通图,若G的边点割原子的顶点数大于2,则G中的最长圈C上至少有3条可去边.

证明假设对G中任一最长圈C,最多只有2条可去边.由定理4知,|E(C)∩ER(G)|≥2.因此C上恰有2条可去边.设E(C)∩ER(G)={e1,e2},记E0=E(C)-{e1,e2}⊆EN(G).取uw∈E0及G的分离分解(uw,S′;A′,B′),其中u∈A′,w∈B′.此时有(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-边点割断片,则A′一定包含一个E0-边点割端片,设A是包含在A′中的E0-边点割端片,取对应的分离分解(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对应的分离分解(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的点割,故|X4|≥3;同理|X2|≥3,由|X2|+|X4|=6可得|X2|=|X4|=3.因为|S|=|T|=3,所以|S∩C|=|A∩T|,|B∩T|=|S∩D|.此时A∩D={z},否则|A∩D|≥2,则(xz,X2;A∩D,B∪C)是G的分离组,且xz∈E0,易知A∩D是包含在A中的E0-边点割断片,且|A∩D|<|A|与A是E0-边点割端片矛盾.故A∩D={z},由D是G的连通分支且|D|≥3可知D∩S≠ø.

情况1.1若|D∩S|=|B∩T|=3,则|X1|=0,从而{y,z}将是G的2-点割,矛盾.

情况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-点割,矛盾.令A∩T={a},C∩S={b},D∩S={u,v}.ab∈E(G),否则,若ab不属于E(G),则{x,u,v}是G的3-点割,矛盾.令e′=ab,S′={x}∪{u,v},A′=A-{x},B′=G-e′-S′-A′,则有(e′,S′;A′,B′)是G中的分离分解,其中A′是G的E0-边点割断片且 |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.此时我们说A∩C={x},否则若|A∩C|≥2,则X1∪{x}是G的3-点割,矛盾.此时|A|=2,与|A|≥3矛盾.

(ii) 若|S∩T|=1,则|C∩S|=|A∩T|=1,此时|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} 都不空.

不失一般性,设e2∈E(A′)∪〈A′,S〉,e1∈E(B′)∪〈B′,S〉.设A是一个包含在A′中的E0-边点割端片,因而存在一个分离分解(xy,S;A,B),其中x∈A,y∈B,xy∈E0,A⊆A′.显然此时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的一个端点为x,另一个端点属于S.不失一般性,令e2=xa,则a在A-{x}中有邻点,设为q(否则,{x,b,c}将是G的一个3-点割,矛盾).由于A是G的连通子图,故A中必有一条连接顶点x和q的路P.于是可得一个新的圈C-xa+aq+P,显然它所含的顶点数比C多,矛盾.因此(E(A)∪〈A,S〉)∩E0≠ø,设uz∈(E(A)∪〈A,S〉)∩E0,取uz对应的一个分离分解(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的讨论可得矛盾.现设x≠u.X1,X2,X3和X4的定义类似情况1.由对称性不妨设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=ø.令A1=A∩C,S1=X1∪{z},B1=G-A1-S1-xy,(xy,S1;A1,B1) 是G的分离分解,xy∈E0,A1是包含在A中的边点割断片,与A是E0-边点割端片矛盾.

若|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的一个点割,因此|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-边点割断片,与A是G中的E0-边点割端片矛盾.故C∩S≠ø,从而T∩A≠ø.

若|X1|≥3,则|X3|≤3,B∩D=ø,|B|=|B∩T|≤2,矛盾.所以|X1|≤2.又X1∪{y,z}是G的点割,由G的4连通性得|X1|≥2,所以|X1|=2.令A1=A∩C,S1=X1∪{z},B1=G-xy-A1-S1,则(xy,S1;A1,B1)是G的分离分解且xy∈E0,|A1|<|A|,与A是E0-边点割端片矛盾.

情况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,此时|X1|=2,矛盾.

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

根据对称性,类似情况2.3的讨论可得矛盾.

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

由B∩C≠ø,可得|X4|≥3,从而|X2|≤3,A∩D=ø.此时A∩T≠ø,否则A=A∩C,从而|A∩C|≥3.因为X1是G-uz-xy的点割,所以|X1|≥2.又D∩S≠ø,得|X1|=2.令A1=A-{u},S1=X1∪{u},B1=G-xy-S1-A1,则G有一分离分解(xy,S1;A1,B1),且A1是包含在A中的E0-边点割断片,矛盾.因此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,此时|S∩C|=1,|S∩T|=0,|B∩T|=2.这时|X1|=2.令A1=A∩C,S1=X1∪{z},B1=G-xy-S1-A1,则G有一分离分解(xy,S1;A1,B1),且A1是包含在A中的E0-边点割断片,矛盾.

情况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,令A1=A-u,S1=X1∪{u},B1=G-xy-S1-A1,则G有一分离分解(xy,S1;A1,B1),且A1是包含在A中的E0-边点割断片,矛盾.

(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.此时|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.此时|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,进而有B∩C=ø,故有|C|=2,矛盾.

故上述定理5成立.

参考文献：

[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连通图中可去边的一些性质[J].广西师范大学学报,1996,14(1):12-17.

[6]尹建华.4连通图的可去边与4连通图的构造[J].系统科学与数学,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]吴吉昌,李学良.4连通图中圈上的可去边和可收缩边[J].厦门大学学报(自然科学版),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

基金项目：国家自然科学基金(11301217)；福建省自然科学基金(2013J01014)；福建省高等学校新世纪优秀人才(JA14168)

中图分类号:O 157.5

文献标志码：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].厦门大学学报(自然科学版)，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)