趙芳雨,冶福龍,李亞寧,火博豐

(青海師范大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院,青海 西寧 810016)

1 引言

圖的生成圈問題,包括哈密頓圈問題和歐拉生成子圖問題,是圖論的一個重要課題.關(guān)于生成圈問題有很多結(jié)果,其中熟知的一個結(jié)論是哈密頓圈關(guān)于最小度的充分條件[1,2].1988年,Catlin[3]證明了對于2-邊連通簡單圖G,若點數(shù)n>16且最小度δ(G)>n/5-1,圖G是超歐拉的.賴虹建[4]教授改進了這個結(jié)果,他證明了2-邊連通簡單圖G,點數(shù)n≥31,圍長g(G)>4,最小度δ(G)>n/10,圖G是超歐拉的.李萍等人在擬陣中研究超歐拉性,通過把圖的最小度轉(zhuǎn)換成擬陣的余圍長的方法,在擬陣中推廣了Catlin的結(jié)果,找到了正則擬陣具有生成圏(即具有超歐拉性的)的一個關(guān)于余圍長下界的充分條件[5].火博豐[6]等人在擬陣中推廣了賴虹建的結(jié)果,將正則擬陣具有生成圈的余圍長充分條件做了改進,得到更好的下界.

為改進使簡單正則擬陣具有超歐拉性的余圍長的下界,需要考慮i-連通擬陣在i-和情形下的相關(guān)性質(zhì).其中比較重要的是擬陣為i-和時,子式之一是余可圖擬陣的情形.在這種情形下,余可圖子擬陣中合格子集的存在性就變得非常重要.我們改進了文獻[7]中的證明方法,證明了合格子集在余圍長較小下界下的存在性.

本文所提及的圖與擬陣都是有限且無自環(huán)的.未定義的符號和術(shù)語,與圖相關(guān)的可以在文獻[1]中找到,與擬陣相關(guān)的可以在文獻[2]中找到.

設(shè)G為一個圖,用V(G)和E(G)分別表示圖G的頂點集和邊集.令H為G的連通子圖,則G/H是從圖G中通過收縮H的所有邊并刪去所形成的自環(huán),用VH代替H得到的圖.設(shè)G是一個圖,κ(G),κ′(G),δ(G),Δ(G),g(G)分別表示圖G的連通度,邊連通度,最小度,最大度,圍長.關(guān)于這些圖參數(shù)的一個熟知的結(jié)果是δ(G)≥κ′(G)≥κ(G).

2 預(yù)備知識

Whitney[8]在1935年最早提出擬陣的概念,他抽象了圖論中的無圈圖和線性代數(shù)中線性無關(guān)概念的共同特征,給出了公理化的定義.對于集合E上的擬陣M,分別定義rM,B(M),C(M)為M的秩函數(shù)、M基的集合和M圈的集合.

一個擬陣M是一個有序?qū)?E,Ι),其中E是一個有限集合,Ι?2E是E中子集的集合,它們滿足以下的公理:

(Ι1)?∈Ι.

(Ι2)若I∈Ι,及I′?I,則I′∈Ι.

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

集合Ι中的元素稱為擬陣M的獨立集.因此公理(Ι1)-(Ι3)為擬陣的獨立集公理.

設(shè)M(E,Ι)是一個擬陣.若子集X∈2E-Ι,則X稱為M的一個相關(guān)集.極小的相關(guān)集稱作極小圈(circuit).一般地,擬陣中的cycle指的是極小相關(guān)集(circuits)的不交并.設(shè)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同構(gòu)于某個圖的余圈擬陣,M就稱為是一個余可圖擬陣.擬陣的子式就是擬陣通過收縮或限制的運算而得到的擬陣.若擬陣與二元域上一個矩陣的列向量空間同構(gòu),則稱擬陣為二元擬陣;若擬陣與一個全幺模矩陣的列向量空間同構(gòu),則稱擬陣為正則擬陣.顯然正則擬陣一定是二元擬陣.

設(shè)M為集合E上的擬陣.如果X?E,λM(X)=r(X)+r(E-X)-r(M)被稱作連通函數(shù),顯然λ(E-X)=λ(X).設(shè)k是一個正整數(shù),對于X?E(M),如果λ(X)

定義2.1[2]對i∈{1,2},設(shè)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環(huán)或余環(huán),且|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為二元域上如下矩陣的向量擬陣:

根據(jù)R10的定義,我們可以觀察到R10為超歐拉的.

定理2.2[9](Seymour) 對于一個連通正則擬陣M,下列條件之一必須成立:

(1)M是可圖擬陣、余可圖擬陣或M?R10;

(2)M是2-連通的且M=M1⊕2M2是M1和M2的2-和,每個Mi(i=1,2)同構(gòu)于M的一個真子式,其中M2要么是可圖擬陣、余可圖擬陣要么同構(gòu)于R10;

(3)M是3-連通的且M=M1⊕3M2是M1和M2的非平凡的3-和,每個Mi(i=1,2)同構(gòu)于M的一個真子式,其中M2是可圖擬陣或余可圖擬陣.

對于一個連通圖G,用τ(G)表示G中邊不交的生成樹的最大數(shù)目.類似地, 在擬陣中,用τ(M)表示M中不交基的最大數(shù)目.若G是個連通圖,那么τ(G)=τ(M(G)).

定義2.3[7]設(shè)M是一個二元擬陣,如果τ(M|N)≥2或者N∈C(M)且|N|≤3,則子集N在M中是合格的.如果M由一個合格子集生成,那么擬陣M就是合格的.我們對一個二元擬陣M,r(M)>0運行以下算法:

(1)令M0:=M;

(2)對于每個i=0,1,…,執(zhí)行以下操作:

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

(2-2)如果Mi沒有合格子集或者Mi中的每個合格子集N滿足r(N)=r(Mi),則停止.

當(dāng)算法停止時,得到的擬陣為M的二元約簡擬陣.

定理2.4[2,10]設(shè)M1和M2為兩個二元擬陣,

(1)M=M1⊕2M2是連通的當(dāng)且僅當(dāng)M1和M2是連通的.

(2)設(shè)M是一個簡單3-連通的二元擬陣,如果M=M1⊕3M2,那么M1和M2都是連通的.特別地,如果M1和M2是兩個簡單擬陣,那么M1和M2都是3-連通的.

在Catlin文獻[7]中以及火博豐文獻[6]中,有下列關(guān)于擬陣強度與分?jǐn)?shù)蔭度的結(jié)論.

定理2.5 設(shè)p和q是整數(shù)且p>q>0,設(shè)M是一個擬陣且r(M)>0,下列每個都成立:

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

李萍在文獻[9]中討論了在2-和與3-和情形下,擬陣的子式的秩與擬陣的秩之間的關(guān)系,得到下面引理:

引理2.7[5]令i∈{2,3}為一個整數(shù),M為i-連通二元擬陣,使得M中的其中一個i-和同構(gòu)于R10或可圖擬陣、余可圖擬陣.存在二元擬陣M1和M2且M=M1⊕iM2,使得M2同構(gòu)于R10或可圖擬陣、余可圖擬陣滿足r(M)≥2r(M2)-i+1或r(M2)≤(r(M)+i-1)/2.

命題2.8[2]設(shè)G是無環(huán)且沒有孤立點的圖,|V(G)|≥3,那么M(G)是連通擬陣當(dāng)且僅當(dāng)G是2-連通圖.

命題2.9[2]設(shè)M是基礎(chǔ)集E上的擬陣.若X?E,那么λM(X)=λM*(X).因此M是n-連通的當(dāng)且僅當(dāng)M*是n-連通的.

命題2.10[2]設(shè)M是基礎(chǔ)集E上的擬陣,T是E的子集,那么M/T=(M*T)*.

命題2.11[2]令G是一個圖,則對所有的E(G)的子集T都有M(G)/T=M(G/T).

3 主要結(jié)論

由正則擬陣的Seymour分解定理,當(dāng)M=M1⊕iM2,M是i-連通的(i=2,3).定理2.4(2)是尹君等[10]得到的一個結(jié)論,即在M為3-連通簡單正則擬陣且M=M1⊕3M2時,若M2為簡單擬陣,則M2為3-連通的,一般情況下M2為2-連通的.

設(shè)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展示了一個圖的極小三邊割所有可能出現(xiàn)的情形.圖G刪除極小三邊割Z后必有兩個連通分支,因此圖5中Gi不連通的情形不可能出現(xiàn).圖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中至多有三個點的度數(shù)至少為1,其余點的度數(shù)至少為4.此外,設(shè)g(G1)g(G2)分別表示圖G-Z的兩個分支G1和G2的圍長.由圖的圍長定義顯然有g(shù)(Gi)≥g(G),圖G中任何兩個距離小于圍長減2的點,它們的鄰點集合必不相交.因此我們可以用廣探法得到一棵以v為根的樹T,使得樹T中從v到葉子點的最短距離是小于圍長一半的最大整數(shù).我們得到下面的定理:

定理3.1 設(shè)G是2-連通圖,Z是G的一個極小三邊割,G1和G2是G-Z的兩個連通分支.對每個i∈{1,2},令ni=|V(Gi)|,Ui=V(Z)∩V(Gi),其中U2至少有兩個點.設(shè)G2中最大度點v的度dG2(v)=t≥4,令δ是G2中除U2之外所有點的最小度,g為圖G的圍長.那么

證明我們從G-Z的其中一個分支出發(fā),利用廣探法去找這個分支的頂點數(shù)的下界,這個下界當(dāng)然也是圖G的頂點數(shù)n的下界.下面我們討論圖1至圖3的情形,從G-Z中具有Z中三個點的分支出發(fā),不妨設(shè)這個分支為G2,并設(shè)G2中與邊割Z關(guān)聯(lián)的點集U2={u1,u2,u3}.由δ(G/Z)≥4可知對于任意u∈V(G2)-U2,dG2(u)=dG(u)≥4.我們規(guī)定從G2的最大度點v點出發(fā)用廣探法得到的樹中點v所在的層數(shù)為1,設(shè)3個頂點u1,u2,u3分別位于第k1,k2,k3層.

(1)當(dāng)g=2h+1時,設(shè)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的度,因此廣探法得到的樹的頂點數(shù)會更大.我們可以用上述結(jié)果作為圍長為奇數(shù)時圖1至圖3的三種情形下圖G的頂點數(shù)的下界.對于圖4的情形,設(shè)G2中與邊割Z關(guān)聯(lián)的點集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)當(dāng)g=2h時,設(shè)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的度,因此廣探法得到的樹的頂點數(shù)會更大.我們可以用上述結(jié)果作為圍長為偶數(shù)時圖1至圖3的三種情形下圖G的頂點數(shù)的下界.

對于圖4的情形,設(shè)G2中與邊割Z關(guān)聯(lián)的點集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類似的圖的頂點數(shù),給出了圍長和最小度條件下的頂點數(shù)的下界:

命題3.2 設(shè)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缺點是圍長條件要求較高,優(yōu)點是點數(shù)的下界更好.

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

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

(1)

由t≥δ,

(2)

(3)

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

(4)

(5)

由t≥δ,

(6)

當(dāng)x≥4時,f′(x)>0,故f(x)在[4,+∞)上為增函數(shù).因此我們得到

(7)

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

(8)