徐保根，羅 茜，丁宗鵬

（華東交通大學基礎科學學院江西南昌330013）

1 引言及定義

文中所指的圖均為無向簡單圖，文中未說明的符號和術語同文獻[1]。

設G為一個圖，對于任意v，則NG(v)表示v點在G中的鄰域，dG(v)= ||NG(v)表示v點在G中的度，NG[v]=NG(v)∪{v}稱為v點的閉鄰域，δ和Δ分別為圖G的最小度和最大度，有時，NG[v]和dG(v)分別簡記為N[v]和d(v)。

設G和H為兩個點不交的圖，在G∪H中將G的每個頂點與H的每個頂點均鄰接起來，所得的圖稱為G與H的聯(lián)圖，記為G∨H。

對于兩個點不交的圖G和H，則G與H的乘積圖記為G×H，其定義為

E

設G為一個圖，D?V(G)，如果對于V(G)D中的每個頂點v，存在u∈D，使得u與v在G中鄰接，則稱D為G的一個控制集，容量最小的控制集包含的點數(shù)稱為G的控制數(shù)，記為γ(G)。

圖的控制理論是圖論中的重要分支，美國圖論學者W.T.Haynes等[2]在1998年出版的專著較為系統(tǒng)地綜述了這一領域的一些主要研究成果。在1977年，E.J.Cockayne和S.T.Hedetniemi[3]引入了圖的集控制概念并研究圖的集控制數(shù)，B.Zelinka[4-5]在圖的集控制方面做了大量工作，得出了集控制數(shù)與圖的其它參數(shù)之間的關系，如集控制數(shù)與線性點蔭度的關系[4]等。

定義1[3]設G是一個圖，如果V(G)能劃分為t個兩兩不交的控制集Di(i=1，2，...，t)，則稱G有t-控制集劃分。圖G的集控制數(shù)記為d(G)，其定義為:d(G)=max｛t|存在G的t-控制集劃分｝。

對于任何圖G，由于D=V(G)本身就是G的一個控制集，故d(G)總是存在的，并且不難證明下面的結論。

引理1[6]對任意圖G，均有d(G)≤1+δ(G)。且v1鄰接v2，或者v1=v2且u1鄰接u2｝。

在本文中，我們主要研究乘積圖與聯(lián)圖的集控制問題，給出這兩種圖集控制數(shù)的界限，并確定了一些特殊性圖的集控制數(shù)，這包括Km×Kn和Pm×Pn等。

2 主要結果及其證明

首先給出兩個圖的乘積圖與聯(lián)圖的集控制數(shù)的界限，然后確定Km×Kn和Pm×Pn的集控制數(shù)。定理1 對于任意n階圖G和m階圖H，均有

并且此上界和下界均是可達的。

1）先證max{n，m} ≥d(G×H)，不妨設n≥m，即證n≥t。

（反證）假若n≤t-1，由定義知:V(G×H)能劃分為t個兩兩不交的控制集Di(i=1，2，…，t)，即

V(G×H)=D1∪D2∪…∪Dt，并且Di∩Dj=? (1≤i≠j≤t)，注意到，故上述劃分中存在一個Dk，使得

?u∈V1，v∈V2，由乘積圖的定義知:圖G×H中的點(u，v)不與Dk中的任何點相鄰，這與Dk為G×H的控制集矛盾，從而n≥t。

2）下面證明d(G×H)≥max{d(G)，d(H)} 。

記d(G)=p，d(H)=q，不妨設p≥q，將V(G)劃分為p個兩兩不交的控制集Ai(i=1，2，…，p)，即V(G)=A1∪A2∪…∪Ap，并且Ai∩Aj=?(1≤i≠j≤p)。

現(xiàn)將V(G×H)分成p個子集如下

由于每個Ai均是G的控制集，故每個Di均是G×H的控制集，即d(G×H)≥p。

特殊地，當G=Kn為n階完全圖，且n≥m時，定理給出的上、下界限均可達。至此，定理1證畢。

注意到d(Kn)=n，故由上述定理1可直接得到下面兩個推論。

推論1 設n和m為整數(shù)，且n≥m，則對任意m階圖H，均有d(Kn×H)=n。

推論2 對于任意正整數(shù)m和n，均有d(Km×Kn)=max{m，n} 。

定理2 對于任意n階圖G和m階圖H，均有

并且此上界和下界均是可達的。

證明 不妨設n≥m。記先證d(G∨H)≥m。只需將V(G∨H)劃分為m個控制集即可，事實上，可令

可見上述每個Di(i=1，2，…，m)均為G∨H的控制集，即d(G∨H)≥m。

下面證明d(G∨H)≤min{m+d(G)，n+d(H)} 。

由對稱性，只需證明d(G∨H)≤m+d(G)即可。記d(G∨H)=t，d(G)=r。

（反證）假若t≥m+r+1，由定義知V(G∨H)能劃分為t個圖G∨H的控制集，即

V(G∨H)=D1∪D2∪…∪Dt，且Di∩Dj=?(1≤i≠j≤t)。注意到 |V(H)|=m，t≥m+r+1，故這些控制集中至少有r+1個控制集均不包含圖H中的點，這r+1個控制集記為Di1，Di2，…，Di(r+1)，它們均不包含圖H中的點，且均為G∨H的控制集，故每個Dij(j=1，2，…，r+1)均為圖G的控制集，注意到其為兩兩不交的，從而d(G)≥r+1，矛盾。定理2證畢。

定理3 對于任意正整數(shù)m≥3和n≥2，均有d(Pm×Pn)=3

證明 令G=Pm×Pn，可見δ(G)=2，由引理1知d(G)≤3。

E下面只需將V(G)劃分為3個控制集V(G)=D1∪D2∪D3。

情況1 當n≡0(m od3) 時，令

情況2 當n≡1(m od3) 時，令V=V1∪V2，其中，V1中的點可以仿照情況1進行劃分，我們只需對V2中的點進行劃分即可。那么

情況3 當n≡2(m od3) 時，令V=V1∪V2，

綜上所述，V(G)能劃分為3個控制集，定理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].北京:科學出版社，2008:103-113.