熊瑋,張啟慧
(新疆大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院,新疆 烏魯木齊 830046)
令G是一個簡單無向圖,用V(G)和E(G)分別表示圖G的頂點(diǎn)集和邊集.經(jīng)過G的每條邊的跡稱為G的Euler跡,G的環(huán)游是指經(jīng)過G的每條邊至少一次的閉途徑.歐拉環(huán)游是指經(jīng)過每條邊恰好一次的環(huán)游,包含歐拉環(huán)游的圖稱為歐拉圖,歐拉圖的度能被2整除.包含所有點(diǎn)的歐拉子圖稱為歐拉生成子圖.例如文獻(xiàn)[1]研究了Hamilton圖的生成子圖問題.若一個圖不是歐拉的,也不含有生成歐拉子圖,則考慮它是否可以加邊成歐拉圖,即歐拉生成母圖.例如文獻(xiàn)[2]研究了歐拉母圖的樹數(shù)條件.類似于歐拉生成母圖的研究,我們首次研究度能被3整除的生成母圖.
本文研究的內(nèi)容是一般圖以及樹圖是否存在度能被3整除的生成母圖.隨著圖階數(shù)的增加,每個圖的度能被3整除的生成母圖不唯一,所以研究增加邊數(shù)最少滿足要求的生成母圖很有意義,即最優(yōu)生成母圖的構(gòu)造.
圖G的頂點(diǎn)v的度記為dG(v).稱G′是G的生成母圖,如果V(G′)=V(G),E(G′)?E(G).若H是G的子圖,G中H的補(bǔ)圖是指子圖G?E(H),記為H(G).包含G的每個頂點(diǎn)的路稱為G的Hamilton路,G的Hamilton圈是指包含G的每個頂點(diǎn)的圈,包含Hamilton圈的圖稱為Hamilton圖.未給出的術(shù)語見文獻(xiàn)[3].
定義1一個圖G的能被3整除的最優(yōu)生成母圖是指圖G加最少的邊得到的度能被3整除的生成母圖,以下簡稱為最優(yōu)母圖.
定義2定義符號[d(v)]3,用來表示將頂點(diǎn)v的度增加至和d(v)最相近且大于d(v)的3的倍數(shù).
定理[3]1設(shè)G為任意無向圖,|E(G)|=ε,則
命題[3]1樹Tn至少有兩個一度頂點(diǎn).
Dirac’s定理[3]若G是簡單圖且|V(G)|≥3,δ(G)≥,則G是哈密爾頓的.
Tutte’s定理[3]記O(G)為G的奇分支的個數(shù),G有完美匹配,當(dāng)且僅當(dāng)O(G?S)≤|S|,?S ∈V(G).
圖G的階數(shù)n<4時,?v ∈G,maxdG(v)<3,所以沒有度能被3整除的生成母圖.因此本文只考慮圖的階數(shù)n ≥4的情形.
圖G增加最少的邊得到度能被3整除的生成母圖,即每個頂點(diǎn)增加最少的度.在構(gòu)造圖G的度能被3整除的生成母圖時,設(shè)v ∈V(G),將頂點(diǎn)v的度增加至和d(v)最相近且大于d(v)的3的倍數(shù),記為[d(v)]3,若此時能生成度能被3整除的生成母圖,該母圖是圖G的最優(yōu)母圖;若此時不存在度能被3整除的生成母圖,考慮將其中一個頂點(diǎn)增加至[d(v)]3+3度時是否存在滿足要求的生成母圖,若不存在就按上述方法繼續(xù)進(jìn)行構(gòu)造.
圖的每個頂點(diǎn)v的度增加至3度時存在生成母圖,則該生成母圖是3正則圖,顯然3正則圖是最優(yōu)母圖.
命題2設(shè)G′為G的度能被3整除的生成母圖,則G到G′需增加的度和為偶數(shù).
證明由定理1知任意圖G所有頂點(diǎn)的度和為偶數(shù),G′所有頂點(diǎn)的度和也為偶數(shù),所以是偶數(shù),故命題成立.
定理2設(shè)G為簡單圖,如果|V(G)|=3k+1(k=1,2,···),則G存在度能被3整除的生成母圖.
證明階為3k+1的簡單圖其最大度為3k,故只要將每個頂點(diǎn)與其余頂點(diǎn)均相連,所得生成母圖每個頂點(diǎn)的度都是3k且為完全圖,即為度能被3整除的生成母圖.
定理3若|V(G)|=3k(k=1,2,···),△(G)≤?1,則G存在度能被3整除的生成母圖.
證明設(shè)G是G的補(bǔ)圖,由△(G)≤?1,得由Dirac’s定理,G中有Hamilton圈C.將G加邊至完全圖Kn,設(shè)v ∈V(Kn),則=3k?1,則Kn?C,即為G的度能被3整除的生成母圖.
定理4設(shè)|V(G)|=3k+2,且k為偶數(shù).若G有完美匹配M,則G存在度能被3整除的生成母圖.
證明將G加邊至完全圖Kn,設(shè)v ∈V(Kn),則dKn(v)=3k+1,則Kn?M為G的度能被3整除的生成母圖.
具有n個頂點(diǎn)的路為Pn,記Pn=v1v2···vn.稱二部圖K1,n?1是n階星圖,記為Sn,Sn中與其余頂點(diǎn)都相鄰的點(diǎn)稱為中心點(diǎn),記為s.將n階星圖Sn的1度頂點(diǎn)連成圈,所得圖稱為n階輪圖,記為Wn.兩個星圖的中心點(diǎn)用一條邊相連,所得的圖稱為雙星圖Sm,n,兩個中心點(diǎn)分別記為s1,s2,與s1相鄰的點(diǎn)記為ui(i=1,2,···,m),與s2相鄰的點(diǎn)記為vi(i=1,2,···,n).下面給出了路圖、星圖和雙星圖度能被3整除的生成母圖的完全刻畫.
定理5對于路Pn,當(dāng)n=4或n ≥6時Pn存在度能被3整除的生成母圖;當(dāng)n=5時Pn沒有度能被3整除的生成母圖.
證明設(shè)路Pn=v1v2···vn,其度能被3整除的生成母圖記為,下面按Pn的階數(shù)分類討論.
情形1當(dāng)n=4時,由定理2知Pn存在度能被3整除的生成母圖K4,且K4是P4的最優(yōu)母圖.
情形2當(dāng)n=5時,若P5存在度能被3整除的生成母圖,而≤4,則中所有頂點(diǎn)的度只能為3,此時需為兩端點(diǎn)各加2度,中間3個頂點(diǎn)各加1度,共增加7度,由命題1知P5沒有度能被3整除的生成母圖.
情形3.1當(dāng)n ≥6時且n為偶數(shù)時,將Pn加邊使其有度能被3整除的生成母圖,先考慮將兩端點(diǎn)各增加2度,其余頂點(diǎn)各增加1度,共增加n+2度,由命題1知可能存在度能被3整除的生成母圖,下證其存在性.由n ≥6,v1與v2是不同的兩頂點(diǎn),與vn是不同的兩頂點(diǎn),加邊則每個頂點(diǎn)都只需1度即可被3整除,n是偶數(shù),增加邊集E1={vivj|i+j=n+1},生成母圖的邊集=E(Pn)∪E1,所得生成母圖是3正則圖,見圖1(左),故路Pn在n ≥6時且n為偶數(shù)時存在度能被3整除.
情形3.2當(dāng)n ≥6時且n為奇數(shù)時,將Pn加邊使其有度能被3整除的生成母圖,先考慮將兩端點(diǎn)各增加2度,其余頂點(diǎn)各增加1度,共增加n+2度,由命題1知不存在度能被3整除的生成母圖,所以在此基礎(chǔ)上給一個頂點(diǎn)再增加3度,即將一個頂點(diǎn)加邊至6度,此時需增加n+5度,由命題1知Pn可能存在度能被3整除的生成母圖,下證其存在性.不妨設(shè)6度頂點(diǎn)為,Pn加邊由n ≥6,增加的邊不是重邊.邊集E2={v1vn∪vivj|i+j=n+1},生成母圖的邊集為=E(Pn)∪E2,所得生成母圖除點(diǎn)外均為3度點(diǎn),見圖1(右),故路Pn在n ≥6時且n為奇數(shù)時存在度能被3整除.
圖1 情形3.1、3.2圖示Fig 1 Figures of subcases 3.1 and 3.2
現(xiàn)已證明路圖Pn在當(dāng)n=4或n ≥6時Pn存在度能被3整除的生成母圖,下面構(gòu)造出增加邊數(shù)最少生成的度能被3整除的生成母圖,即最優(yōu)母圖.對于路圖,若將所有頂點(diǎn)加邊至3度時存在生成母圖,則該母圖就是最優(yōu)母圖;若將所有頂點(diǎn)加邊至3度時不存在生成母圖,考慮將其中一個頂點(diǎn)加邊至6度,其余頂點(diǎn)仍加邊至3度時是否存在生成母圖,以此類推構(gòu)造路圖的最優(yōu)母圖.
推論1定理5的證明中構(gòu)造出的母圖是最優(yōu)母圖.
證明將Pn加邊使其有度能被3整除的生成母圖且增加的邊數(shù)最少,即每個頂點(diǎn)增加最少的度,只要將每個頂點(diǎn)的度都增加至[d(v)]3,如果存在每個頂點(diǎn)的度為[d(v)]3的生成母圖,則為最優(yōu)母圖.當(dāng)增加的度和為奇數(shù)時由命題1知不存在最優(yōu)母圖,在此基礎(chǔ)上給任一頂點(diǎn)再增加3度由命題1知可能存在最優(yōu)母圖,其存在性證明同定理5;當(dāng)增加的度和為偶數(shù)時由定理1知可能存在最優(yōu)母圖,其存在性證明同定理5.
定理6星圖Sn,當(dāng)n=3k+1(k=1,2,···)時,存在度能被3整除的生成母圖;當(dāng)n=3k+2或n=3k (k=1,2,···)時不存在度能被3整除的生成母圖.
證明在星圖Sn中,d(s)=n?1.當(dāng)n=3k+1(k=1,2,···)時,由定理1知存在度能被3整除的生成母圖且是完全圖Kn.
當(dāng)n=3k+2或n=3k(k=1,2,···)時,有d(s)=3k+1或d(s)=3k?1,不能被3整除,且s已與其余所有的點(diǎn)相連,所以d(s)不能加邊至[d(v)]3度,故Sn不存在度能被3整除的生成母圖.
推論2星圖Sn,當(dāng)n=3k+1(k=1,2,···)時的最優(yōu)母圖為Wn.
證明當(dāng)n=3k+1 (k=1,2,···)時,d(s)=3k.由定理1知存在度能被3整除的生成母圖且是完全圖Kn.但Kn不是Sn的最優(yōu)母圖,中心點(diǎn)s的度已能被3整除,其余點(diǎn)均為2度,只要將1度頂點(diǎn)連成圈,所得的生成母圖是輪圖Wn的度能被3整除且是最優(yōu)母圖.
定理7雙星圖Sm,n存在度能被3整除的生成母圖.
證明對于雙星圖Sm,n,我們分以下7種情況討論:
情形1當(dāng)m=2,n=2時,顯然有度能被3整除的生成母圖且是3正則圖.當(dāng)m=2,n=3時,d(s2)=4,設(shè)v是Sm,n的生成母圖的頂點(diǎn),則maxd(v)=6,為得到S2,3的度能被3整除的生成母圖,S1已滿足要求,S2必須加相聯(lián)的邊至6度,且只能與u1和u2分別相連,再將u1和u2相連,v1,v2,v3連成圈,所得生成母圖的度能被3整除.
情形2當(dāng)m=3k1,n=3k2(k1,k2=1,2,···)時,有d(s1)=3k1+1,d(s2)=3k2+1,設(shè)v ∈Sm,n,將v加邊至[d(v)]3度,所有的頂點(diǎn)都只需2度,其度即可被3整除,需增加的度和為6k1+6k2+4,由命題1知Sm,n可能存在度能被3整除的生成母圖,下證其存在性.s1只能與N={vi|i=1,2,···,n}中的任意兩個頂點(diǎn)相連,不妨設(shè)為v1和vn,s2只能與M={ui|i=1,2,···,m}中的任意兩個頂點(diǎn)相連,不妨設(shè)為u1和um,再將u1,u2,···,um和v1,v2,···,vn分別連成路,所得的生成母圖就是度能被3整除的生成母圖.
情形3當(dāng)m=3k1,n=3k2+1(k1,k2=1,2,···)時,d(s1)=3k1+1,d(s2)=3k2+1,設(shè)v ∈Sm,n,將v加邊至[d(v)]3度,需增加6k1+6k2+5度,由命題1知不存在度能被3整除的生成母圖,現(xiàn)考慮在此基礎(chǔ)上將其中任意一個頂點(diǎn)再增加3度,此時需增加6k1+6k2+8度,由命題1知可能存在度能被3整除的生成母圖,下證其存在性.s1只能與N={vi|i=1,2,···,n}中的任意兩個頂點(diǎn)相連,不妨設(shè)為v1和vn,s2只能與M={ui|i=1,2,···,m}中的任一頂點(diǎn)相連,不妨設(shè)為u1,經(jīng)驗(yàn)證再增加3度的頂點(diǎn)的選取不影響構(gòu)造滿足要求的生成母圖,不妨將頂點(diǎn)v1增加至6度,將v1與u1,u2,um,v1分別相連,將u2,u3,···,um和v1,v2,···,vn分別連成路,所得的生成母圖就是度能被3整除的生成母圖.
情形4當(dāng)m=3k1,n=3k2+2(k1,k2=1,2,···)時,d(s1)=3k1+1,d(s2)=3k2+3,設(shè)v ∈Sm,n,將v加邊至[d(v)]3度,s2已滿足要求,其余所有的頂點(diǎn)均只需2度其度即可被3整除,需增加的度和為6k1+6k2+6,由命題1知Sm,n可能存在度能被3整除的生成母圖,下證其存在性.s1只能與N={vi|i=1,2,···,n}中的任意兩頂點(diǎn)相連,不妨設(shè)為v1和vn,將u1,u2,u3,···,um連成圈,將v1,v2,···,vn連成路,所得的生成母圖就是度能被3整除的生成母圖.
圖2從左到右分別表示當(dāng)m=3k1,n=3k2;m=3k1,n=3k2+1;m=3k1,n=3k2+2時Sm,n的度能被3整除的生成母圖的一種情況.
圖2 情形2、3和4的圖示Fig 2 Figures of subcases 2,3 and 4
情形5m=3k1+1,n=3k2+1(k1,k2=1,2,···)時,d(s1)=3k1+2,d(s2)=3k2+2,設(shè)v ∈Sm,n,將v加邊至[d(v)]3度,s1和s2需增加1度,其余所有的頂點(diǎn)均需2度即可被3整除,需增加的度和為6k1+6k2+6,由命題1知Sm,n可能存在度能被3整除的生成母圖,下證其存在性.s1只能與N={vi|i=1,2,···,n}中的任一頂點(diǎn)相連,不妨設(shè)為v1,s2只能與M={ui|i=1,2,···,m}中的任一頂點(diǎn)相連,不妨設(shè)為u1,連接um和vn,將u1,u2,u3,···,um連成路,將v1,v2,···,vn連成路,所得的生成母圖就是度能被3整除的生成母圖.
情形6m=3k1+1,n=3k2+2 (k1,k2=1,2,···)時,d(s1)=3k1+2,d(s2)=3k2+3,設(shè)v ∈Sm,n,將v加邊至[d(v)]3度,需增加6k1+6k2+7度,由命題1知不存在度能被3整除的生成母圖,現(xiàn)考慮在此基礎(chǔ)上將其中任意一個頂點(diǎn)再增加3度,此時需增加6k1+6k2+10度,由命題1知可能存在度能被3整除的生成母圖,下證其存在性.s1只能與N={vi|i=1,2,···,n}中的任一頂點(diǎn)相連,不妨設(shè)為v1,s2已滿足要求,經(jīng)驗(yàn)證再增加3度的頂點(diǎn)的選取不影響構(gòu)造滿足要求的生成母圖,不妨將頂點(diǎn)v1增加至6度,將v1與u1,u2,um,v2分別相連,將u1,u2,u3,···,um和v1,v2,···,vn分別連成路,所得的生成母圖就是度能被3整除的生成母圖.
情形7m=3k1+2,n=3k2+2(k1,k2=1,2,···)時,d(s1)=3k1+3,d(s2)=3k2+3,設(shè)v ∈Sm,n,將v加邊至v ∈[d(v)]3度,s1和s2已滿足要求,其余所有的頂點(diǎn)均需2度即可被3整除,需增加的度和為6k1+6k2+8,由命題1知Sm,n可能存在度能被3整除的生成母圖,下證其存在性.將u1,u2,u3,···,um連成圈,v1,v2,···,vn連成圈,所得的生成母圖就是度能被3整除的生成母圖.
圖3從左到右依次是當(dāng)m=3k1+1,n=3k2+1;m=3k1+1,n=3k2+2 和m=3k1+2,n=3k2+2時Sm,n的度能被3整除的生成母圖的一種情況.
圖3 情形5、6和7的圖示Fig 3 Figures of subcases 5,6 and 7
命題3設(shè)T為樹圖,?S ?V,ω(?S)≤2.
證明反證,假設(shè)ω(?S)≥3,設(shè)C1,C2,C3為?S的3個連通分支,則分別在C1,C2,C3中任取一點(diǎn)v1,v2,v3,由于在中v1,v2,v3之間無邊,因此在T中,v1v2v3形成一個3圈,與樹無圈矛盾,故ω(?S)≤2.
命題4若樹圖T不是星,則
證明反證,設(shè)有兩個連通分支C1,C2,若|C1|≥2,|C2|≥2,則在T中C1,C2中的點(diǎn)構(gòu)成一個長度大于等于4的圈,矛盾.故|C1|=1或|C2|=1,則T是星,矛盾.
定理8樹圖T不為星圖,樹圖T的頂點(diǎn)數(shù)n=3k+2,且n為偶數(shù),則T有度能被3整除的生成母圖.
證明由定理4,只需證T有完美匹配.由Tutte’s定理,只需證下證|S|,?S ?V.
情形1S=?,由于T不是星圖,由命題4知,=1.由n為偶數(shù),=0,故
情形2|S|=1,由命題3知,≤2,由于n是偶數(shù),故≤1.
情形3|S|≥2,由命題3知,
故樹T不為星圖,樹T的頂點(diǎn)數(shù)n=3k+2,且n為偶數(shù)時,T有度能被3整除的生成母圖.
樹圖Tn,由定理2知,當(dāng)n=3k+1時存在度能被3整除的生成母圖;由定理8知,當(dāng)樹Tn不為星圖,頂點(diǎn)數(shù)n=3k+2,且n為偶數(shù)時,T有度能被3整除的生成母圖;由定理3知,當(dāng)n=3k且△(T)≤?1時存在度能被3整除的生成母圖.對于頂點(diǎn)數(shù)n=3k+2,且n為奇數(shù)的情況尚未討論,推測同樣存在.
新疆大學(xué)學(xué)報(bào)(自然科學(xué)版)(中英文)2021年6期