關(guān)于圖的集控制數(shù)

徐保根，羅 茜，丁宗鵬

（華東交通大學(xué)基礎(chǔ)科學(xué)學(xué)院江西南昌330013）

1 引言及定義

文中所指的圖均為無向簡單圖，文中未說明的符號和術(shù)語同文獻(xiàn)[1]。

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

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

對于兩個(gè)點(diǎn)不交的圖G和H，則G與H的乘積圖記為G×H，其定義為

E

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

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

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

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

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

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

2 主要結(jié)果及其證明

首先給出兩個(gè)圖的乘積圖與聯(lián)圖的集控制數(shù)的界限，然后確定Km×Kn和Pm×Pn的集控制數(shù)。定理1 對于任意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，則對任意m階圖H，均有d(Kn×H)=n。

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

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

并且此上界和下界均是可達(dá)的。

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

可見上述每個(gè)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è)圖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 對于任意正整數(shù)m≥3和n≥2，均有d(Pm×Pn)=3

證明 令G=Pm×Pn，可見δ(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)行劃分，我們只需對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.