似星樹與路的乘積圖的任意可分性

張盼盼, 劉鳳霞, 孟吉翔

(新疆大學 數學與系統科學學院, 烏魯木齊 830046)

1 引言與預備知識

設圖G=(V,E)是階為n的簡單圖, 正整數序列λ=(λ1,λ2,…,λp)是一個非遞減序列. 如果λ1+λ2+…+λp=n, 則稱λ是G的可允許序列. 如果λ是一個可允許序列, 且存在對點集V的一個劃分(V1,V2,…,Vp), 使得每個Vi導出一個階為λi的G的連通子圖, 則稱λ是G的可實現序列, 且(V1,V2,…,Vp)是序列λ在G中的實現, 每個子圖G[Vi]稱為圖G的λi分支. 如果每個可允許序列都是可實現的, 則稱G是任意可分圖(簡稱AP圖或AVD圖)[1]. 如果圖G含一條Hamilton路, 則稱圖G為可跡圖. 顯然, 每個可跡圖都是任意可分圖. 當圖G的階為偶數時,G有完美匹配等價于序列(2,2,…,2)是G的可實現序列； 當圖G的階為奇數時,G有幾乎完美匹配等價于序列(1,2,…,2)是G的可實現序列. 因此, 任意可分圖一定有完美匹配或幾乎完美匹配, 從而一個圖有完美匹配或者幾乎完美匹配的必要條件是該圖為任意可分圖.

如果圖G的生成樹是任意可分圖, 則圖G是任意可分圖. Horňk等[2]證明了如果樹T是任意可分的, 則T的最大度至多為6, 并且提出了任意可分樹的最大度至多為4的猜想. 該猜想被Barth等[3]證明, 得到了任意可分樹的最大度至多為4, 且每個4度頂點與一個葉子點相鄰的結論. Cichacz等[4]刻畫了4個葉子點的毛毛蟲樹的任意可分性, 并展示了最大度為3或4的兩類任意可分樹. Marczyk[5]證明了對階為n的連通圖G, 當獨立數至多為n/2, 且任意一對不相鄰頂點的度和至少為n-3時, 圖G是任意可分圖或者同構于兩個例外圖. Horňk等[6]證明了對階數n≥20的連通圖G, 任意兩個不相鄰頂點的度和至少為n-5, 則G有完美匹配或幾乎完美匹配. Baudon等[7]提出了任意可分圖和可跡圖的笛卡爾積圖是任意可分圖的猜想, 證明了可跡圖的頂點數至多為4時猜想成立, 并證明了當兩個任意可分圖中至少有一個階數至多為4時, 這兩個任意可分圖的笛卡爾積圖也是任意可分圖. 文獻[8]證明了樹T的最大度至多為l+1時, 如果T中有一條包含所有(l+1)度頂點的路, 則T□Cl是任意可分圖. 此外, 文獻[9-11]研究了樹的笛卡爾積圖的相關性質.

本文將兩個圖G和H的乘積圖記為G??H, 其頂點集

V(G??H)={(g,h)|g∈V(G)且h∈V(H)},

邊集

E(G??H)={(g,h)(g′,h′)|gg′∈E(G)且hh′∈E(H)或gg′∈E(G)且h=h′}.

用S=S(a1,a2,…,at,b1,b2,…,bs)表示最大度為t+s的似星樹, 設d(v)=t+s, 則

S-{v}=Pa1∪Pa2∪…∪Pat∪Pb1∪Pb2∪…∪Pbs,

其中Pai=vi1vi2…viai,Pbj=v(t+j)1v(t+j)2…v(t+j)bj, 且ai(1≤i≤t)是奇數,bj(1≤j≤s)是偶數,

本文給出在t和s的不同取值下, 乘積圖S??Pl的任意可分性.

2 主要結果

設S=S(a1,a2,…,at,b1,b2,…,bs)是最大度為t+s的似星樹, 假設t+s≥2. 設G=S??Pl, 其中|Pl|=l≥2, 圖Sp是S在G中的第p個拷貝, 其對應的點集為

其中vp是Sp的最大度點. 似星樹S(a,b,c)是階為1+a+b+c, 由一個3度頂點連接3條長分別為a,b,c的不交路的圖. 本文將序列(λ1,…,λ1,…,λp,…,λp)記為((λ1)k1,…,(λp)kp), 對i∈{1,2,…,p},λi出現ki次. 兩個正整數a和b的最大公因子記為gcd(a,b).

命題1對于圖G及其可允許序列λ=(λ1,λ2,…,λp), 存在(V1,V2,…,Vm), 滿足

|V1|=λ1, |V2|=λ2, …, |Vm|=λm,

且G[Vj]連通, 其中1≤j≤m, 如果

V-V1-V2-…-Vm=V0,

G[V0]有一條Hamilton路, 則必存在Vm+1,Vm+2,…,Vp, 滿足|Vi|=λi且G[Vi]連通, 其中m+1≤i≤p. 因此, 圖G的可允許序列λ=(λ1,λ2,…,λp)是可實現的.

引理1(Tutte’s定理)[12]設圖G是階為偶數的連通圖, 則圖G有完美匹配當且僅當對所有的點子集S?V, 均有o(G-S)≤|S|.

引理2[13]設圖G是階為奇數的連通圖, 則圖G有幾乎完美匹配當且僅當對所有的點子集S?V, 均有o(G-S)≤|S|+1.

引理3[1,14]設圖G是似星樹S(1,a,b), 且1≤a≤b, 則圖G是任意可分圖當且僅當

gcd(a+1,b+1)=1.

定理1設S=S(a1,a2,…,at,b1,b2,…,bs)是似星樹, 其中t≥2, 則圖S??Pl不是任意可分圖.

證明: 設G=S??Pl, 為證明圖G不是任意可分圖, 只需找到一個不可實現的序列, 下面證明圖G不含完美匹配或幾乎完美匹配.

取G的獨立集

圖G-I的奇分支數為o(G-I), 如圖1(A)所示. 設m=a1+a2+…+at,Si是S在圖G中的第i個拷貝, 則有

因為t≥2, 則o(G-I)-|I|≥2. 由引理1和引理2知, 圖G不含完美匹配或幾乎完美匹配. 因此, 圖G不是任意可分圖.

定理2設S=S(a1,a2,…,at,b1,b2,…,bs)是似星樹, 其中t=0, 則圖S??Pl不是任意可分圖.

證明: 設G=S??Pl, 由t+s≥2,t=0知s≥2, 與定理1的證明類似. 令圖G的獨立集

o(G-I)是圖G-I的奇分支數, 如圖1(B)所示. 設m=b1+b2+…+bs,Si是S在圖G中的第i個拷貝. 顯然,G-I是孤立點, 則有

由引理1和引理2知, 圖G不含完美匹配或幾乎完美匹配. 因此, 圖G不是任意可分圖.

定理1和定理2分別討論了t≥2和t=0的情形, 下面討論t=1的情形.

定理3設S=S(a1,a2,…,at,b1,b2,…,bs)是似星樹, 其中t=1,s=1, 則圖S??Pl是任意可分圖.

圖1 圖G的拷貝Si

證明: 設G=S??Pl, 當l為偶數時, 可找到圖G中的一條Hamilton路P, 如圖2所示, 即

圖2 圖S(a1,b1)??Pl(l為偶數)

當l為奇數時, 同理可找到圖G中的一條Hamilton路. 因此, 圖G是任意可分圖.

定理4設S=S(a1,a2,…,at,b1,b2,…,bs)是似星樹, 其中t=1,s=2, 即S=S(a1,b1,b2), 則圖S??Pl是任意可分圖.

證明: 下面僅討論l為奇數的情形, 當l為偶數時同理可證. 令

1) 如圖3所示,a1=1. 此時, 設

則

圖3 圖S(1,b1,b2)??Pl

① 當r=1時, 令Vr={vl-1}.

2) 如圖4所示,a1≥3. 此時, 令

圖4 圖S(a1,b1,b2)??Pl

gcd(2,b1l+(a1-1)(l-1)+1)=1.

由引理3, 似星樹S(1,1,b1l+(a1-1)(l-1))是任意可分圖. 因此, 序列λ在圖G中是可實現的.

因此, 序列λ是圖G的可實現序列.

定理5設S=S(a1,a2,…,at,b1,b2,…,bs)是似星樹, 其中t=1,s≥3, 且Δ(S)≥l+2. 如果b1=b2=…=bs, 則圖S??Pl不是任意可分圖.

證明: 設G=S??Pl, |G|=n,Δ(S)=k. 令q=b1=b2=…=bs且b=ql, 則

n=(k-1)b+(a1+1)l.

考慮到圖G-{v1,v2,…,vl}連通分支的階為a1l和b, 下面分兩種情形討論.

1) 若a1

c=n-l(b+1)=(k-1)b+a1l-bl>a1l.

若λ是G的可實現序列, 則每個b+1分支必須包含一個點vi,i∈{1,2,…,l}. 因為c≥a1l+1, 故c分支必包含一個點vi,i∈{1,2,…,l}, 共需(l+1)個點, 與l=|{vi|i=1,2,…,l}|矛盾.

2) 若a1>b1, 則如果k=l+2, 可考慮G的可允許序列λ=((b+1)l,a1l+1,c), 其中c=b-1. 如果k>l+2, 可考慮G的可允許序列λ=((b+1)l+1,a1l+1,c), 其中c=(k-l-2)b-2.

在這兩種情形下, 每個b+1分支必包含一個點vi,i∈{1,2,…,l}, 每個a1l+1分支也必包含一個點vi,i∈{1,2,…,l}, 與l=|{vi|i=1,2,…,l}|矛盾, 故λ不是G的可實現序列, 圖S??Pl不是任意可分圖.