李雨欣 蘇貴福

(北京化工大學(xué) 數(shù)理學(xué)院,北京 100029)

引 言

若圖G中每個(gè)頂點(diǎn)的度都為r,則稱圖G為r-正則圖。用Sn、Pn、Cn和Kn分別表示n個(gè)頂點(diǎn)的星圖、路、圈和完全圖,Km,n表示完全二部圖,其中二部劃分為(X,Y),且|X|=m,|Y|=n。對(duì)于兩個(gè)圖G和H,若V(G)∩V(H)=?,則稱G與H不相交。兩個(gè)不相交的圖G和H的并記為G∪H,而nG表示n個(gè)G的不交并。

在圖G中,若頂點(diǎn)子集S的導(dǎo)出子圖的最大度等于0,則稱S為圖G的一個(gè)獨(dú)立集;若S不為其他獨(dú)立集的真子集,則稱S為一個(gè)極大獨(dú)立集。圖中包含頂點(diǎn)個(gè)數(shù)最多的獨(dú)立集稱為最大獨(dú)立集。在20世紀(jì)60年代Moser等[1]提出如下計(jì)數(shù)問(wèn)題:n個(gè)頂點(diǎn)的一般圖上極大獨(dú)立集的最大數(shù)目是多少?相應(yīng)的極圖又是什么?隨后在文獻(xiàn)[1]中他們證明了對(duì)于n個(gè)頂點(diǎn)的圖G,其極大獨(dú)立集個(gè)數(shù)至多為3n/3個(gè),當(dāng)n≡0(mod 3)且G為n/3個(gè)K3的不交并時(shí)達(dá)到極值;對(duì)于其他的n值,他們也給出了精確的極值并刻畫了極圖。

此后,學(xué)者們聚焦于不同圖類上的極大獨(dú)立集和最大獨(dú)立集的計(jì)數(shù)問(wèn)題的研究,特別是在連通圖[2-3]、無(wú)三角形的圖[4]、二部圖[5]、單圈圖[6]和最多含有r個(gè)圈的圖[7]等方面獲得重要結(jié)果。由于圖子結(jié)構(gòu)同社團(tuán)結(jié)構(gòu)間的關(guān)系密切,研究其他圖子結(jié)構(gòu)的計(jì)數(shù)問(wèn)題也具有重要意義,因此學(xué)者們將計(jì)數(shù)對(duì)象擴(kuò)展得到其他極值結(jié)果,如最小支配集[8-9]、極小支配集[10]、最小連通點(diǎn)覆蓋[11]、最小反饋點(diǎn)集[12]以及極小反饋點(diǎn)集[13]等圖子結(jié)構(gòu)。圖子結(jié)構(gòu)的計(jì)數(shù)問(wèn)題成為圖論和組合數(shù)學(xué)領(lǐng)域的一個(gè)研究熱點(diǎn)。

給定圖G=(V,E),若頂點(diǎn)子集F在G中的導(dǎo)出子圖的最大度至多為1,則稱F為圖G的一個(gè)分離集;若F不為其他分離集的真子集,則稱F為一個(gè)極大分離集。圖中包含頂點(diǎn)個(gè)數(shù)最多的分離集稱為最大分離集。顯然圖的獨(dú)立集同時(shí)也是其分離集。1981年Yannakakis[14]首次提出分離集的概念,并證明了最大分離集問(wèn)題在二部圖上是NP-困難的。近幾十年來(lái),學(xué)者們對(duì)不同圖類上的最大分離集問(wèn)題的計(jì)算復(fù)雜性作了深入研究,詳見文獻(xiàn)[15-16]。

1 相關(guān)引理

用MD(G)表示圖G中所有極大分離集構(gòu)成的集合,并記φ(G)=|MD(G)|。

下面的引理1顯然成立。

引理1 對(duì)于兩個(gè)不相交的圖G和H,有

φ(G∪H)=φ(G)·φ(H)

引理2 設(shè)v是任意圖G中的頂點(diǎn),有

若存在頂點(diǎn)w∈N(v)使得N[w]?N[v],則

證明:對(duì)圖G中的極大分離集進(jìn)行劃分,有

若存在頂點(diǎn)w∈N(v)使得N[w]?N[v],則φ(G,v0)=0。因此

引理3 設(shè)v是圖G中的一懸掛點(diǎn),w是其鄰點(diǎn),則

證明:若在圖G中存在極大分離集F,使得懸掛點(diǎn)v∈F,則頂點(diǎn)w∈F且dG[F](w)=1。因此

引理4 若圖G中有一頂點(diǎn)w恰與兩個(gè)懸掛點(diǎn)v1和v2相鄰,則

證明:圖G中極大分離集所構(gòu)成的集合可分為以下3類:不包含v1和v2;包含v1和v2;包含v1和w或包含v2和w。因此

引理5 設(shè)Pn是含有n個(gè)頂點(diǎn)的路,則φ(Pn)＜0.81an。

證明:對(duì)頂點(diǎn)數(shù)n作歸納。當(dāng)n≤4時(shí),易驗(yàn)證結(jié)論成立。因此,在后續(xù)討論中總假設(shè)n≥5,且對(duì)任意的Pn-1結(jié)論均成立。設(shè)頂點(diǎn)v為Pn的懸掛點(diǎn),w是其鄰點(diǎn),而u是w的另一鄰點(diǎn)。由歸納假設(shè)及引理3,有

φ(Pn)＜φ(Pn-4)+φ(Pn-2)+φ(Pn-3)＜0.81an-4+0.81an-2+0.81an-3=0.81an(a-2+a-3+a-4)＜0.81an

引理6 設(shè)Cn是含有n個(gè)頂點(diǎn)的圈,則φ(Cn)≤an,等號(hào)成立當(dāng)且僅當(dāng)n=4。

證明:當(dāng)n=3或n=4時(shí),易驗(yàn)證結(jié)論成立。因此,后續(xù)討論中假設(shè)n≥5。根據(jù)引理2和引理5,有

φ(Cn)＜φ(Pn-1)+φ(Pn-3)+2φ(Pn-4)＜0.81an-1+0.81an-3+2×0.81an-4=0.81an(a-1+a-3+2a-4)＜0.81an

2 主要結(jié)論及證明

2.1 主要結(jié)論

本節(jié)研究n個(gè)頂點(diǎn)且最大度至多為3的圖中極大分離集的最大個(gè)數(shù),得到如下主要定理。

2.2 定理1的證明

對(duì)頂點(diǎn)個(gè)數(shù)n作歸納。當(dāng)n＜6時(shí),易驗(yàn)證結(jié)論成立。因此,在后續(xù)討論中假設(shè)n≥6,且對(duì)于任意最大度至多為3的n-1階圖結(jié)論均成立。

當(dāng)圖G不連通時(shí),設(shè)G1和G2是G的兩個(gè)連通分支,且|V(G)|=|V(G1)|+|V(G2)|=n1+n2。顯然G1和G2皆為最大度至多為3的圖,根據(jù)歸納假設(shè)及引理1,有

等號(hào)成立當(dāng)且僅當(dāng)G1和G2同時(shí)滿足定理中的極圖結(jié)構(gòu),亦即圖G滿足定理中的極圖結(jié)構(gòu)。

接下來(lái)考慮圖G為連通圖的情形。為方便后續(xù)證明,給出以下兩個(gè)斷言。

斷言1 若連通圖G包含懸掛點(diǎn)v,則φ(G)＜an。

證明:記v的鄰點(diǎn)為w。由歸納假設(shè)及引理4,有

φ(G)≤(d(w)-1)an-d(w)-1+an-2+an-d(w)-1=an(d(w)a-d(w)-1+a-2)

注意到n≥6且Δ≤3,則有d(w)∈{2,3}。經(jīng)計(jì)算可得φ(G)＜an。

斷言2 若連通圖G中存在頂點(diǎn)u使得N(u)={v,w},且d(w)=3,d(v)=2,則φ(G)＜an。

證明:設(shè)N(v)={u,t}。當(dāng)t=w時(shí),有N[u]?N[w],故圖G-w?uv∪(G-{u,v,w})。由歸納假設(shè)知

φ(G)≤an-3+2an-4+an-5=an(a-3+2a-4+a-5)＜an

當(dāng)t≠w時(shí),分以下兩種情況討論。

情況1t∈N(w),N(w)={u,t,s}

當(dāng)d(t)=2時(shí),圖G-w?P3∪(G-{w,u,v,t}),則由歸納假設(shè)知

φ(G)≤3an-4+an-4+3an-5=an(4a-4+3a-5)＜an

當(dāng)d(t)=3時(shí),如果s∈N(t)且d(s)=2,則V(G)={u,v,w,t,s},易得φ(G)=6＜a5。否則,圖G-w包含懸掛點(diǎn)u,且dG-w(t)=2,這就說(shuō)明圖G-N[w]?v∪(G-{u,v,w,t,s})。因此,有

φ(G-w)≤an-5+an-3+an-4

φ(G)≤φ(G-w)+an-5+3an-5≤an(a-3+a-4+5a-5)＜an

情況2t?N(w),N(w)={u,s1,s2}

當(dāng)d(s1)=2且N[s1]={w,s1,s2}?N[w]時(shí),圖G-w包含懸掛點(diǎn)u,于是由歸納假設(shè)得

φ(G-w)≤an-5+an-3+an-4

φ(G)≤φ(G-w)+an-4+2an-5≤an(a-3+2a-4+3a-5)＜an

否則,設(shè)A=N(t)-{v,s1,s2}。當(dāng)A=?時(shí),圖G-w中包含懸掛點(diǎn)u,此時(shí)容易發(fā)現(xiàn)圖G-N[w]?vt∪(G-{u,v,w,t,s1,s2})。因此

φ(G-w)≤an-5+an-3+an-4

φ(G)≤φ(G-w)+an-6+3an-5≤an(a-3+a-4+4a-5+a-6)＜an

當(dāng)A≠?時(shí),有1≤|A|≤2。對(duì)于vi∈A,記Bi=N(vi)-{t,s1,s2},其中1≤i≤2。若對(duì)于任意Bi都有Bi=?,則圖G-w包含懸掛點(diǎn)u,且

G-N[w]?P3∪(G-{u,v,w,t,s1,s2,v1})

或

G-N[w]?S4∪(G-{u,v,w,t,s1,s2,v1,v2})

于是,由歸納假設(shè)知

φ(G-w)≤an-5+an-3+an-4

φ(G-N[w])≤max{3an-7,4an-8}=3an-7

φ(G)≤φ(G-w)+φ(G-N[w])+3an-5≤an(a-3+a-4+4a-5+3a-7)＜an

若存在Bi使得Bi≠?,則圖G-w包含懸掛點(diǎn)u,圖G-N[w]包含懸掛點(diǎn)v。因此

φ(G-w)≤an-5+an-3+an-4

φ(G-N[w])≤max{an-9+an-7+2an-8,an-8+an-6+an-7,2an-9+an-6+an-8}=an-8+an-6+an-7

φ(G)≤φ(G-w)+φ(G-N[w])+3an-5≤an(a-3+a-4+4a-5+a-6+a-7+a-8)＜an

綜上,斷言2得證。

由斷言1可知,當(dāng)δ=1時(shí),有φ(G)＜an。由引理6可知,若Δ=δ=2,則φ(G)≤an。因此,接下來(lái)只需研究Δ=3且δ=2的圖以及3-正則圖。

情形ⅠΔ=3且δ=2

在這種情形下,圖中必有一個(gè)三度頂點(diǎn)v和二度頂點(diǎn)u相鄰。設(shè)N(u)={v,t},N(v)={u,v1,v2}。由斷言2可知,當(dāng)d(t)=2時(shí),有φ(G)＜an。因此,在后續(xù)討論中總假設(shè)d(t)=3。

當(dāng)t=v1時(shí),有N[u]?N[v]。若d(v2)=2且v1～v2,則圖V(G)={v,u,v1,v2}且φ(G)=6=a4。否則,圖G-v包含懸掛點(diǎn)u,于是由歸納假設(shè)得

φ(G-v)≤an-5+an-3+an-4

φ(G)≤φ(G-v)+2an-4+an-5≤an(a-3+3a-4+2a-5)＜an

φ(G-v)≤max{an-6+an-4+2an-5,2an-6+an-3+an-5}=2an-6+an-3+an-5

E1≤max{an-6+2an-5,an-5+2an-6,3an-5}=3an-5

φ(G)≤φ(G-v)+an-4+E1≤an(a-3+a-4+4a-5+2a-6)＜an

情形Ⅱ 3-正則圖

若G為一n階3-正則連通圖,分兩種情況進(jìn)行討論。

情況1 圖G中不含C3

設(shè)v為圖G的一個(gè)頂點(diǎn),N(v)={v1,v2,v3}且N(v2)={v,s,t},如圖1所示。

圖1 圖G中不含C3Fig.1 Case where G doesn't contain C3

若N(s)=N(t)={v1,v2,v3},則G?K3,3,進(jìn)而φ(G)=11＜a6。

若N(s)∩{v1,v3}=?且|N(t)∩N(s)|=3,即圖G具有圖2所示子結(jié)構(gòu),由歸納假設(shè)有

圖2 s不與v1、v3相鄰,且s與t有相同鄰點(diǎn)Fig.2 Case where s isn't adjacent to v1,v3 and s,t have same neighborhoods

φ(G-v-s)≤2an-7+an-4+an-6

φ(G-v)≤φ(G-v-s)+an-5+an-6+2an-7φ(G)≤φ(G-v)+an-4+3an-6≤an(2a-4+a-5+5a-6+4a-7)＜an

否則,1≤|N(t)∩N(s)|≤2,即圖G-v-s具有圖3所示的3種子結(jié)構(gòu)之一。根據(jù)歸納假設(shè)及引理4,有

φ(G-v-s)≤max{an-8+an-5+2an-6,2an-8+an-4+an-6,an-7+an-8+an-4+an-6}=an-7+an-8+an-4+an-6

E2≤max{3an-6,2an-6+an-7,an-6+2an-7}=3an-6

φ(G-v)≤φ(G-v-s)+an-5+E2

φ(G)≤φ(G-v)+an-4+3an-6≤an(2a-4+a-5+7a-6+a-7+a-8)＜an

情況2 圖G中包含C3

設(shè)v、v1、v2是C3的3個(gè)頂點(diǎn),N(v1)={v,v2,t}且N(v2)={v,v1,s}。

子情況2.1N(v3)∩(N(v1)∪N(v2))={v}(圖4)。

圖4 v1,v2,v3有共同鄰點(diǎn)vFig.4 Case where v1,v2,v3 have a common neighborhood v

φ(G-v3-v1)≤an-7+an-4+an-5

φ(G-v3)≤φ(G-v3-v1)+an-5+an-6+an-7

φ(G)≤φ(G-v3)+an-4+2an-5+an-6≤an(2a-4+4a-5+2a-6+2a-7)＜an

子情況2.2 圖G具有以下兩種子結(jié)構(gòu)(圖5):

圖5 s的鄰點(diǎn)分布Fig.5 Neighborhood distribution of s

(1)當(dāng)t≠v3時(shí),有N(s)={t,v2,v3};

(2)當(dāng)t=v3時(shí),有N(s)={w,v2,v3}。

因圖G-N[s]?vv1∪(G-N[s]-{v,v1}),則

φ(G)≤an-1+an-6+3an-6=an(a-1+4a-6)＜an

圖6 v1,v3有兩個(gè)公共鄰點(diǎn)且非公共鄰點(diǎn)不相鄰Fig.6 Case where v1,v3 have two common neighborhoods and the different neighborhoods are nonadjacent

注意到在圖G-v3中有N[v]?N[v1],且圖G-v3-v1?vv2∪(G-{v,v1,v2,v3}),則由歸納假設(shè)可得

φ(G-v3)≤an-4+2an-5+an-7

φ(G)≤φ(G-v3)+an-4+2an-5+an-6≤an(2a-4+4a-5+a-6+a-7)＜an

子情況2.4 當(dāng)v3=t=s時(shí)有圖G?K4,直接計(jì)算可知φ(G)=6=a4。

綜上,定理1得證。

3 結(jié)束語(yǔ)