徐保根,羅 茜,丁宗鵬
(華東交通大學(xué)基礎(chǔ)科學(xué)學(xué)院江西南昌330013)
文中所指的圖均為無(wú)向簡(jiǎn)單圖,文中未說(shuō)明的符號(hào)和術(shù)語(yǔ)同文獻(xiàn)[1]。
設(shè)G為一個(gè)圖,對(duì)于任意v,則NG(v)表示v點(diǎn)在G中的鄰域,dG(v)= ||NG(v)表示v點(diǎn)在G中的度,NG[v]=NG(v)∪{v}稱(chēng)為v點(diǎn)的閉鄰域,δ和Δ分別為圖G的最小度和最大度,有時(shí),NG[v]和dG(v)分別簡(jiǎn)記為N[v]和d(v)。
設(shè)G和H為兩個(gè)點(diǎn)不交的圖,在G∪H中將G的每個(gè)頂點(diǎn)與H的每個(gè)頂點(diǎn)均鄰接起來(lái),所得的圖稱(chēng)為G與H的聯(lián)圖,記為G∨H。
對(duì)于兩個(gè)點(diǎn)不交的圖G和H,則G與H的乘積圖記為G×H,其定義為
E
設(shè)G為一個(gè)圖,D?V(G),如果對(duì)于V(G)D中的每個(gè)頂點(diǎn)v,存在u∈D,使得u與v在G中鄰接,則稱(chēng)D為G的一個(gè)控制集,容量最小的控制集包含的點(diǎn)數(shù)稱(chēng)為G的控制數(shù),記為γ(G)。
圖的控制理論是圖論中的重要分支,美國(guó)圖論學(xué)者W.T.Haynes等[2]在1998年出版的專(zhuān)著較為系統(tǒng)地綜述了這一領(lǐng)域的一些主要研究成果。在1977年,E.J.Cockayne和S.T.Hedetniemi[3]引入了圖的集控制概念并研究圖的集控制數(shù),B.Zelinka[4-5]在圖的集控制方面做了大量工作,得出了集控制數(shù)與圖的其它參數(shù)之間的關(guān)系,如集控制數(shù)與線(xiàn)性點(diǎn)蔭度的關(guān)系[4]等。
定義1[3]設(shè)G是一個(gè)圖,如果V(G)能劃分為t個(gè)兩兩不交的控制集Di(i=1,2,...,t),則稱(chēng)G有t-控制集劃分。圖G的集控制數(shù)記為d(G),其定義為:d(G)=max{t|存在G的t-控制集劃分}。
對(duì)于任何圖G,由于D=V(G)本身就是G的一個(gè)控制集,故d(G)總是存在的,并且不難證明下面的結(jié)論。
引理1[6]對(duì)任意圖G,均有d(G)≤1+δ(G)。且v1鄰接v2,或者v1=v2且u1鄰接u2}。
在本文中,我們主要研究乘積圖與聯(lián)圖的集控制問(wèn)題,給出這兩種圖集控制數(shù)的界限,并確定了一些特殊性圖的集控制數(shù),這包括Km×Kn和Pm×Pn等。
首先給出兩個(gè)圖的乘積圖與聯(lián)圖的集控制數(shù)的界限,然后確定Km×Kn和Pm×Pn的集控制數(shù)。定理1 對(duì)于任意n階圖G和m階圖H,均有
并且此上界和下界均是可達(dá)的。
1)先證max{n,m} ≥d(G×H),不妨設(shè)n≥m,即證n≥t。
(反證)假若n≤t-1,由定義知:V(G×H)能劃分為t個(gè)兩兩不交的控制集Di(i=1,2,…,t),即
V(G×H)=D1∪D2∪…∪Dt,并且Di∩Dj=? (1≤i≠j≤t),注意到,故上述劃分中存在一個(gè)Dk,使得
?u∈V1,v∈V2,由乘積圖的定義知:圖G×H中的點(diǎn)(u,v)不與Dk中的任何點(diǎn)相鄰,這與Dk為G×H的控制集矛盾,從而n≥t。
2)下面證明d(G×H)≥max{d(G),d(H)} 。
記d(G)=p,d(H)=q,不妨設(shè)p≥q,將V(G)劃分為p個(gè)兩兩不交的控制集Ai(i=1,2,…,p),即V(G)=A1∪A2∪…∪Ap,并且Ai∩Aj=?(1≤i≠j≤p)。
現(xiàn)將V(G×H)分成p個(gè)子集如下
由于每個(gè)Ai均是G的控制集,故每個(gè)Di均是G×H的控制集,即d(G×H)≥p。
特殊地,當(dāng)G=Kn為n階完全圖,且n≥m時(shí),定理給出的上、下界限均可達(dá)。至此,定理1證畢。
注意到d(Kn)=n,故由上述定理1可直接得到下面兩個(gè)推論。
推論1 設(shè)n和m為整數(shù),且n≥m,則對(duì)任意m階圖H,均有d(Kn×H)=n。
推論2 對(duì)于任意正整數(shù)m和n,均有d(Km×Kn)=max{m,n} 。
定理2 對(duì)于任意n階圖G和m階圖H,均有
并且此上界和下界均是可達(dá)的。
證明 不妨設(shè)n≥m。記先證d(G∨H)≥m。只需將V(G∨H)劃分為m個(gè)控制集即可,事實(shí)上,可令
可見(jiàn)上述每個(gè)Di(i=1,2,…,m)均為G∨H的控制集,即d(G∨H)≥m。
下面證明d(G∨H)≤min{m+d(G),n+d(H)} 。
由對(duì)稱(chēng)性,只需證明d(G∨H)≤m+d(G)即可。記d(G∨H)=t,d(G)=r。
(反證)假若t≥m+r+1,由定義知V(G∨H)能劃分為t個(gè)圖G∨H的控制集,即
V(G∨H)=D1∪D2∪…∪Dt,且Di∩Dj=?(1≤i≠j≤t)。注意到 |V(H)|=m,t≥m+r+1,故這些控制集中至少有r+1個(gè)控制集均不包含圖H中的點(diǎn),這r+1個(gè)控制集記為Di1,Di2,…,Di(r+1),它們均不包含圖H中的點(diǎn),且均為G∨H的控制集,故每個(gè)Dij(j=1,2,…,r+1)均為圖G的控制集,注意到其為兩兩不交的,從而d(G)≥r+1,矛盾。定理2證畢。
定理3 對(duì)于任意正整數(shù)m≥3和n≥2,均有d(Pm×Pn)=3
證明 令G=Pm×Pn,可見(jiàn)δ(G)=2,由引理1知d(G)≤3。
E下面只需將V(G)劃分為3個(gè)控制集V(G)=D1∪D2∪D3。
情況1 當(dāng)n≡0(m od3) 時(shí),令
情況2 當(dāng)n≡1(m od3) 時(shí),令V=V1∪V2,其中,V1中的點(diǎn)可以仿照情況1進(jìn)行劃分,我們只需對(duì)V2中的點(diǎn)進(jìn)行劃分即可。那么
情況3 當(dāng)n≡2(m od3) 時(shí),令V=V1∪V2,
綜上所述,V(G)能劃分為3個(gè)控制集,定理3證畢。
[1]BOND JA,MURTYV S R.Graph theory with applications[M].Amsterdam:Elsevier,1976:247-250.
[2]HAYNES T W,HEDETNIEMI S T,SLATER P J.Domination in graphs[M].New York:Marcel Dekker INC,1998:150-155.
[3] COCKAYNE E J,HEDETNIEMI S T.Towards a theory of domination in graphs[J].Networks,1977(7):247-261.
[4]ZELINKAB.Domatic number and linear arboricity of cacti[J].Slovaca Math,1986(36):41-54.
[5] ZELINKAB.Domatic number and degrees of vertices of a graph[J].Slovaca Math,1989(39):7-11.
[6]徐保根.圖的控制理論[M].北京:科學(xué)出版社,2008:103-113.