余可图子拟阵中合格子集的存在性

赵芳雨,冶福龙,李亚宁,火博丰

(青海师范大学 数学与统计学院,青海 西宁 810016)

1 引言

图的生成圈问题,包括哈密顿圈问题和欧拉生成子图问题,是图论的一个重要课题.关于生成圈问题有很多结果,其中熟知的一个结论是哈密顿圈关于最小度的充分条件[1,2].1988年,Catlin[3]证明了对于2-边连通简单图G,若点数n>16且最小度δ(G)>n/5-1,图G是超欧拉的.赖虹建[4]教授改进了这个结果,他证明了2-边连通简单图G,点数n≥31,围长g(G)>4,最小度δ(G)>n/10,图G是超欧拉的.李萍等人在拟阵中研究超欧拉性,通过把图的最小度转换成拟阵的余围长的方法,在拟阵中推广了Catlin的结果,找到了正则拟阵具有生成圏(即具有超欧拉性的)的一个关于余围长下界的充分条件[5].火博丰[6]等人在拟阵中推广了赖虹建的结果,将正则拟阵具有生成圈的余围长充分条件做了改进,得到更好的下界.

为改进使简单正则拟阵具有超欧拉性的余围长的下界,需要考虑i-连通拟阵在i-和情形下的相关性质.其中比较重要的是拟阵为i-和时,子式之一是余可图拟阵的情形.在这种情形下,余可图子拟阵中合格子集的存在性就变得非常重要.我们改进了文献[7]中的证明方法,证明了合格子集在余围长较小下界下的存在性.

本文所提及的图与拟阵都是有限且无自环的.未定义的符号和术语,与图相关的可以在文献[1]中找到,与拟阵相关的可以在文献[2]中找到.

设G为一个图,用V(G)和E(G)分别表示图G的顶点集和边集.令H为G的连通子图,则G/H是从图G中通过收缩H的所有边并删去所形成的自环,用VH代替H得到的图.设G是一个图,κ(G),κ′(G),δ(G),Δ(G),g(G)分别表示图G的连通度,边连通度,最小度,最大度,围长.关于这些图参数的一个熟知的结果是δ(G)≥κ′(G)≥κ(G).

2 预备知识

Whitney[8]在1935年最早提出拟阵的概念,他抽象了图论中的无圈图和线性代数中线性无关概念的共同特征,给出了公理化的定义.对于集合E上的拟阵M,分别定义rM,B(M),C(M)为M的秩函数、M基的集合和M圈的集合.

一个拟阵M是一个有序对(E,Ι),其中E是一个有限集合,Ι⊆2E是E中子集的集合,它们满足以下的公理:

(Ι1)∅∈Ι.

(Ι2)若I∈Ι,及I′⊆I,则I′∈Ι.

(Ι3)若I1,I2∈Ι且|I1|<|I2|,则存在e∈I2-I1使得I1∪e∈Ι.

集合Ι中的元素称为拟阵M的独立集.因此公理(Ι1)-(Ι3)为拟阵的独立集公理.

设M(E,Ι)是一个拟阵.若子集X∈2E-Ι,则X称为M的一个相关集.极小的相关集称作极小圈(circuit).一般地,拟阵中的cycle指的是极小相关集(circuits)的不交并.设M(E,Ι)是一个拟阵,C=C(M),则C满足下列极小圈公理:

(C1)∅∉C.

(C2)若C1,C2∈C且C1⊆C2,则C1=C2.

(C3)若C1≠C2,C1,C2∈C并且存在e∈C1∩C2,则恒有C3∈C满足C3⊆(C1∪C2)-e.

容易证明极小圈公理与独立集公理是等价的.极小圈公理中的(C3)称为极小圈消去公理.对于子集X⊆E,M/X和M|X分别定义为拟阵的收缩和拟阵的限制.

若存在某个图G,使得M≅M(G),则称M为可图拟阵.对于图G,我们用M*(G)表示G的圈拟阵的对偶.M*(G)被称作G的余圈拟阵.若拟阵M同构于某个图的余圈拟阵,M就称为是一个余可图拟阵.拟阵的子式就是拟阵通过收缩或限制的运算而得到的拟阵.若拟阵与二元域上一个矩阵的列向量空间同构,则称拟阵为二元拟阵;若拟阵与一个全幺模矩阵的列向量空间同构,则称拟阵为正则拟阵.显然正则拟阵一定是二元拟阵.

设M为集合E上的拟阵.如果X⊂E,λM(X)=r(X)+r(E-X)-r(M)被称作连通函数,显然λ(E-X)=λ(X).设k是一个正整数,对于X⊂E(M),如果λ(X)

定义2.1[2]对i∈{1,2},设Mi是一个二元拟阵且Ei=E(Mi).

(1)如果E1∩E2=∅,且|E1|,|E2|<|E1ΔE2|,M1ΔM2是M1和M2的1-和,定义为M1⊕M2.

(2)如果|E1∩E2|=1且E1∩E2={p},其中p不是M1或M2环或余环,且|E1|,|E2|<|E1ΔE2|,M1ΔM2是M1和M2的2-和,定义为M1⊕2M2.

(3)如果|E1∩E2|=3且E1∩E2=Z,其中Z是M1和M2的一个圈,且Z既不包含M1也不包含M2的任何余圈,|E1|,|E2|<|E1ΔE2|,M1ΔM2是M1和M2的3-和,定义为M1⊕3M2.

令R10为二元域上如下矩阵的向量拟阵:

根据R10的定义,我们可以观察到R10为超欧拉的.

定理2.2[9](Seymour) 对于一个连通正则拟阵M,下列条件之一必须成立:

(1)M是可图拟阵、余可图拟阵或M≅R10;

(2)M是2-连通的且M=M1⊕2M2是M1和M2的2-和,每个Mi(i=1,2)同构于M的一个真子式,其中M2要么是可图拟阵、余可图拟阵要么同构于R10;

(3)M是3-连通的且M=M1⊕3M2是M1和M2的非平凡的3-和,每个Mi(i=1,2)同构于M的一个真子式,其中M2是可图拟阵或余可图拟阵.

对于一个连通图G,用τ(G)表示G中边不交的生成树的最大数目.类似地, 在拟阵中,用τ(M)表示M中不交基的最大数目.若G是个连通图,那么τ(G)=τ(M(G)).

定义2.3[7]设M是一个二元拟阵,如果τ(M|N)≥2或者N∈C(M)且|N|≤3,则子集N在M中是合格的.如果M由一个合格子集生成,那么拟阵M就是合格的.我们对一个二元拟阵M,r(M)>0运行以下算法:

(1)令M0:=M;

(2)对于每个i=0,1,…,执行以下操作:

(2-1)如果Mi有子集N在Mi中为合格的且r(N)

(2-2)如果Mi没有合格子集或者Mi中的每个合格子集N满足r(N)=r(Mi),则停止.

当算法停止时,得到的拟阵为M的二元约简拟阵.

定理2.4[2,10]设M1和M2为两个二元拟阵,

(1)M=M1⊕2M2是连通的当且仅当M1和M2是连通的.

(2)设M是一个简单3-连通的二元拟阵,如果M=M1⊕3M2,那么M1和M2都是连通的.特别地,如果M1和M2是两个简单拟阵,那么M1和M2都是3-连通的.

在Catlin文献[7]中以及火博丰文献[6]中,有下列关于拟阵强度与分数荫度的结论.

定理2.5 设p和q是整数且p>q>0,设M是一个拟阵且r(M)>0,下列每个都成立:

引理2.6[2]对正整数i∈{2,3},若M是i-连通的且M=M1⊕iM2,那么r(M)=r(M1)+r(M2)-i+1.

李萍在文献[9]中讨论了在2-和与3-和情形下,拟阵的子式的秩与拟阵的秩之间的关系,得到下面引理:

引理2.7[5]令i∈{2,3}为一个整数,M为i-连通二元拟阵,使得M中的其中一个i-和同构于R10或可图拟阵、余可图拟阵.存在二元拟阵M1和M2且M=M1⊕iM2,使得M2同构于R10或可图拟阵、余可图拟阵满足r(M)≥2r(M2)-i+1或r(M2)≤(r(M)+i-1)/2.

命题2.8[2]设G是无环且没有孤立点的图,|V(G)|≥3,那么M(G)是连通拟阵当且仅当G是2-连通图.

命题2.9[2]设M是基础集E上的拟阵.若X⊆E,那么λM(X)=λM*(X).因此M是n-连通的当且仅当M*是n-连通的.

命题2.10[2]设M是基础集E上的拟阵,T是E的子集,那么M/T=(M*T)*.

命题2.11[2]令G是一个图,则对所有的E(G)的子集T都有M(G)/T=M(G/T).

3 主要结论

由正则拟阵的Seymour分解定理,当M=M1⊕iM2,M是i-连通的(i=2,3).定理2.4(2)是尹君等[10]得到的一个结论,即在M为3-连通简单正则拟阵且M=M1⊕3M2时,若M2为简单拟阵,则M2为3-连通的,一般情况下M2为2-连通的.

设M=M1⊕3M2为3-连通简单正则拟阵,M2为余可图拟阵,M2≅M*(G).在一般情况下M2为2-连通的,由命题2.9可知M*与M有相同的连通度,即M(G)是2-连通的,从而由命题2.8,我们得到G是2-连通图.由3-和的定义,Z是M1和M2的一个圈,M2≅M*(G),因此Z是M*(G)的一个圈,即是图G的一个极小三边割,G1和G2是G-Z的两个连通分支.

图1至图5展示了一个图的极小三边割所有可能出现的情形.图G删除极小三边割Z后必有两个连通分支,因此图5中Gi不连通的情形不可能出现.图G中的极小三边割为图1至图4的四种情况.

图1 图G中的第一种极小三边割图2 图G中的第二种极小三边割

图3 图G中的第三种极小三边割图4 图G中的第四种极小三边割图5 图G中Gi不连通时三边割非极小

由g(M2)=g(M*(G))=g(M(G)/Z)*=g*(M(G)/Z)=g*(M(G/Z))=κ′(G/Z),可知δ(G/Z)≥κ′(G/Z)=g(M2)≥g(M)≥4.而由G是2-连通图,可知Gi中至多有三个点的度数至少为1,其余点的度数至少为4.此外,设g(G1)g(G2)分别表示图G-Z的两个分支G1和G2的围长.由图的围长定义显然有g(Gi)≥g(G),图G中任何两个距离小于围长减2的点,它们的邻点集合必不相交.因此我们可以用广探法得到一棵以v为根的树T,使得树T中从v到叶子点的最短距离是小于围长一半的最大整数.我们得到下面的定理:

定理3.1 设G是2-连通图,Z是G的一个极小三边割,G1和G2是G-Z的两个连通分支.对每个i∈{1,2},令ni=|V(Gi)|,Ui=V(Z)∩V(Gi),其中U2至少有两个点.设G2中最大度点v的度dG2(v)=t≥4,令δ是G2中除U2之外所有点的最小度,g为图G的围长.那么

证明我们从G-Z的其中一个分支出发,利用广探法去找这个分支的顶点数的下界,这个下界当然也是图G的顶点数n的下界.下面我们讨论图1至图3的情形,从G-Z中具有Z中三个点的分支出发,不妨设这个分支为G2,并设G2中与边割Z关联的点集U2={u1,u2,u3}.由δ(G/Z)≥4可知对于任意u∈V(G2)-U2,dG2(u)=dG(u)≥4.我们规定从G2的最大度点v点出发用广探法得到的树中点v所在的层数为1,设3个顶点u1,u2,u3分别位于第k1,k2,k3层.

(1)当g=2h+1时,设u1≠v,则2≤k1≤k2≤k3≤h+1,有

n≥1+t+t(δ-1)+t(δ-1)2+…+t(δ-1)k1-2+[t(δ-1)k1-1-(δ-2)]+

[t(δ-1)k1-1-(δ-2)](δ-1)+…+[t(δ-1)k1-1-(δ-2)](δ-1)k2-k1-1+

[[t(δ-1)k1-1-(δ-2)](δ-1)k2-k1-(δ-2)]+[[t(δ-1)k1-1-(δ-2)](δ-1)k2-k1-(δ-2)](δ-1)+…+

[[t(δ-1)k1-1-(δ-2)](δ-1)k2-k1-(δ-2)](δ-1)k3-k2-1+

{[[t(δ-1)k1-1-(δ-2)](δ-1)k2-k1-(δ-2)](δ-1)k3-k2-(δ-2)}+

{[[t(δ-1)k1-1-(δ-2)](δ-1)k2-k1-(δ-2)](δ-1)k3-k2-(δ-2)}(δ-1)+…+

{[[t(δ-1)k1-1-(δ-2)](δ-1)k2-k1-(δ-2)](δ-1)k3-k2-(δ-2)}(δ-1)h-k3

=(1+t+t(δ-1)+…+t(δ-1)h-1-[(δ-2)+(δ-2)(δ-1)+…+(δ-2)(δ-1)h-k1]-

[(δ-2)+(δ-2)(δ-1)+…+(δ-2)(δ-1)h-k2]-[(δ-2)+(δ-2)(δ-1)+…+(δ-2)(δ-1)h-k3]

注意到u1=v时并不影响点v的度,因此广探法得到的树的顶点数会更大.我们可以用上述结果作为围长为奇数时图1至图3的三种情形下图G的顶点数的下界.对于图4的情形,设G2中与边割Z关联的点集U2={u1,u2},2个顶点u1,u2分别位于第k1,k2层.

n≥1+t+t(δ-1)+t(δ-1)2+…+t(δ-1)k1-2+[t(δ-1)k1-1-(δ-1)]+[t(δ-1)k1-1-(δ-1)](δ-1)

+…+[t(δ-1)k1-1-(δ-1)](δ-1)k2-k1-1+[[t(δ-1)k1-1-(δ-1)](δ-1)k2-k1-(δ-1)]

+[[t(δ-1)k1-1-(δ-1)](δ-1)k2-k1-(δ-1)](δ-1)+…+

[[t(δ-1)k1-1-(δ-1)](δ-1)k2-k1-(δ-1)](δ-1)h-k2

=(1+t+t(δ-1)+…+t(δ-1)h-1-[(δ-1)+(δ-1)2+…+(δ-1)h-k1+1]-[(δ-1)+(δ-1)2+…+

(δ-1)h-k2+1]

(2)当g=2h时,设u1≠v,2≤k1≤k2≤k3≤h,取点v的异于u1,u2,u3的邻点v0.

n≥2+[(t-1)+(δ-1)]+(t+δ-2)(δ-1)+…+[(t+δ-2)(δ-1)k1-1-(δ-2)]+

[(t+δ-2)(δ-1)k1-1-(δ-2)](δ-1)+…+[(t+δ-2)(δ-1)k1-1-(δ-2)](δ-1)k2-k1-1+

[[(t+δ-2)(δ-1)k1-1-(δ-2)](δ-1)k2-k1-(δ-2)]+[[(t+δ-2)(δ-1)k1-1-(δ-2)]

(δ-1)k2-k1-(δ-2)](δ-1)+…+[[(t+δ-2)(δ-1)k1-1-(δ-2)](δ-1)k2-k1-(δ-2)]

(δ-1)k3-k2-1+{[[(t+δ-2)(δ-1)k1-1-(δ-2)](δ-1)k2-k1-(δ-2)](δ-1)k3-k2-(δ-2)}+

{[[(t+δ-2)(δ-1)k1-1-(δ-2)](δ-1)k2-k1-(δ-2)](δ-1)k3-k2-(δ-2)}(δ-1)+…+

{[[(t+δ-2)(δ-1)k1-1-(δ-2)](δ-1)k2-k1-(δ-2)](δ-1)k3-k2-(δ-2)}(δ-1)h-k3-1

注意到u1=v时并不影响点v的度,因此广探法得到的树的顶点数会更大.我们可以用上述结果作为围长为偶数时图1至图3的三种情形下图G的顶点数的下界.

对于图4的情形,设G2中与边割Z关联的点集U2={u1,u2},2个顶点u1,u2分别位于第k1,k2层.

n≥2+[(t-1)+(δ-1)]+(t+δ-2)(δ-1)+…+[(t+δ-2)(δ-1)k1-1-(δ-1)]+

[(t+δ-2)(δ-1)k1-1-(δ-1)](δ-1)+…+[(t+δ-2)(δ-1)k1-1-(δ-1)](δ-1)k2-k1-1+

[[(t+δ-2)(δ-1)k1-1-(δ-1)](δ-1)k2-k1-(δ-1)]+[[(t+δ-2)(δ-1)k1-1-(δ-1)](δ-1)k2-k1-

(δ-2)](δ-1)+…+[[(t+δ-2)(δ-1)k1-1-(δ-1)](δ-1)k2-k1-(δ-1)](δ-1)h-k2-1

刘瑞芳等在文献[11]中研究了与定理3.2类似的图的顶点数,给出了围长和最小度条件下的顶点数的下界:

命题3.2 设G是简单连通图,X是G的点割,H是G-X的连通分支.若δ:=min{dG(v):v∈V(H)}≥4,|X|≤3,H的围长满足g:=g(H)≥4,那么

比较命题3.2与定理3.1,定理3.1缺点是围长条件要求较高,优点是点数的下界更好.

(i)η(G/Z)≤2;

(ii)M*(G)包含一个非空的合格子集.

(1)

由t≥δ,

(2)

(3)

由(1)、(2)和(3)得

(4)

(5)

由t≥δ,

(6)

当x≥4时,f′(x)>0,故f(x)在[4,+∞)上为增函数.因此我们得到

(7)

由(5)、(6)和(7)得

(8)