宋 曦,陳 琴

(中國計(jì)量大學(xué) 理學(xué)院,浙江 杭州 310018)

圖的控制理論主要研究圖的各種控制參數(shù)的值。1962年Oystein正式提出“控制數(shù)”的概念并于1965年發(fā)表成果[1],之后有關(guān)圖的控制數(shù)問題得到了迅速發(fā)展?？刂萍涂刂茢?shù)的重要性不僅僅體現(xiàn)在理論上,而且在生活中的應(yīng)用也十分廣泛。在許多選址問題上都需要借鑒控制數(shù)問題,比如在某個(gè)城市的小區(qū)之間建立快遞物流服務(wù)站,最少需要建立多少個(gè)服務(wù)站才能保證物流運(yùn)輸?shù)臅惩?。而在?shí)際生活的各種要求限制下,又延伸出許多不同類別的控制數(shù)問題,如全控制數(shù)[2]、羅馬控制數(shù)[3]等。趙敏和陳琴[4]將圖的控制理論與電力網(wǎng)相結(jié)合,研究了幾類電力控制數(shù)為1的平方圖。Goddard等[5]在2014年提出并研究了圖的半全控制集,此后許多學(xué)者對該問題進(jìn)行了研究,并取得豐碩的成果。朱恩強(qiáng)等研究了無爪三正則圖[6]、線圖[7]的半全控制數(shù)。2019年,Henning等[8]證明了平面圖、分裂圖、弦二部圖的半全控制數(shù)對應(yīng)的判定問題是NP-完備的。陳琴等[9]研究了圖的半全控制數(shù)的剖分?jǐn)?shù)。

1 準(zhǔn)備工作設(shè)

G=(V,E)是一個(gè)無向簡單圖,其中V是G的頂點(diǎn)集,E是G的邊集。對于集合D?V,若VD中每個(gè)頂點(diǎn)都至少與D中一個(gè)頂點(diǎn)相鄰,則稱D是G的一個(gè)控制集。G的控制數(shù)是G的最小控制集的頂點(diǎn)個(gè)數(shù),用γ(G)表示。對于集合S?V,若S是G的控制集,且對于S中的每個(gè)頂點(diǎn),在S中都存在另一個(gè)頂點(diǎn)與其距離小于等于2,則稱S是G的半全控制集。G的最小半全控制集的頂點(diǎn)個(gè)數(shù)稱為G的半全控制數(shù),記為γt2(G)。對任意的v∈V,v的開鄰域記為N(v)={u∈V|uv∈E},閉鄰域記為N[v]={v}∪N(v)。用Cn=x1x2…xnx1表示n個(gè)頂點(diǎn)的圈。用Hm表示由m個(gè)六邊形組成的線性六邊形鏈,圖1為H3。由于互為同構(gòu)圖的半全控制數(shù)相同,因此每個(gè)六邊形可以用圖2中的同構(gòu)圖圈C6來代替。為了方便研究,令Hm的頂點(diǎn)集為{xi,j|1≤i≤n,j=1,2},其中n=2m+1,如圖3。對任意的i=1,2…,n,令Yi={xi,j|j=1,2}。

圖1 圖H3Figure 1 Graph H3

圖2 六邊形的同構(gòu)圖圈C6Figure 2 Isomorphic graph C6 of hexagon

圖3 HmFigure 3 Hm

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

引理2.1設(shè)D是Hm+3的一個(gè)最小半全控制集,令n=2m+1,Sn,2為Hm+3中由頂點(diǎn){xij|1≤i≤n,j=1,2}導(dǎo)出的子圖,即Sn,2與Hm同構(gòu),如圖4,則在Hm+3中,有|D∩(Yn+1∪Yn+2∪Yn+3∪Yn+4∪Yn+5∪Yn+6)|≥4。特別地,當(dāng)|D∩(Yn+1∪Yn+2∪Yn+3∪Yn+4∪Yn+5∪Yn+6)|=4時(shí),D∩Sn,2是Sn,2的一個(gè)半全控制集。

圖4 引理2.1中Sn,2與Hm+3Figure 4 Sn,2 and Hm+3 in Lemma 2.1

證明由于N[xn+5,1]∩N[xn+5,2]=?,為了控制xn+5,1和xn+5,2,必有|D∩(Yn+6∪Yn+5∪Yn+4)|≥2。

為了控制xn+2,1,有|D∩N[xn+2,1]|≥1,即|D∩(Yn+1∪Yn+2∪Yn+3)|≥1。

情形1|D∩(Yn+6∪Yn+5∪Yn+4)|≥4

此時(shí)顯然有|D∩(Yn+6∪Yn+5∪Yn+4∪Yn+3∪Yn+2∪Yn+1)|≥5,引理成立。

情形2|D∩(Yn+6∪Yn+5∪Yn+4)|=3

若|D∩(Yn+1∪Yn+2∪Yn+3)|≥2,則引理成立。若|D∩(Yn+1∪Yn+2∪Yn+3)|=1,則一定有|D∩Yn+2|=1。由對稱性不妨設(shè)xn+2,2∈D,此時(shí)

D∩{xn+1,1,xn+1,2,xn+2,1,xn+3,1}=?。

因此xn,1∈D,且與xn,1距離小于等2的點(diǎn)在D∩Sn,2中,即D∩Sn,2是Sn,2的半全控制集,引理成立。

情形3|D∩(Yn+6∪Yn+5∪Yn+4)|=2

若|D∩Yn+4|=2,則xn+6,1和xn+6,2沒有被控制;若|D∩Yn+4|=1,不妨設(shè)xn+4,1∈D,由于N[xn+6,1]∩N[xn+5,2]={xn+6,2},則xn+6,2∈D,但在D中不存在與xn+6,2距離小于等于2的點(diǎn),矛盾。因此|D∩Yn+4|=0。由于

N[xn+3,1]∩N[xn+3,2]=?,

為了控制xn+3,1和xn+3,2,有|D∩(Yn+3∪Yn+2)|≥2。當(dāng)|D∩(Yn+3∪Yn+2)|≥3時(shí)引理成立。接下來討論|D∩(Yn+3∪Yn+2)|=2的情形。不妨設(shè)D∩Yn+1=?,否則引理成立。分以下情形討論。

情形3.1|D∩Yn+2|=0

此時(shí)|D∩Yn|=2。那么D∩Sn,2是Sn,2的半全控制集,引理成立。

情形3.2|D∩Yn+2|=1

由對稱性,可設(shè)D∩Yn+2={xn+2,1}。此時(shí)xn,2∈D,且D中與xn,2的距離小于等于2的點(diǎn)在Sn,2中,即|D∩(Yn+6∪Yn+5∪Yn+4∪Yn+3∪Yn+2∪Yn+1)|=4時(shí),D∩Sn,2是Sn,2的半全控制集,引理成立。

情形3.3|D∩Yn+2|=2

此時(shí)D∩Yn+3=?,|D∩Yn+5|=2。但在D中不存在與xn+5,1和xn+5,2距離小于等于2的點(diǎn)。因此本情形不存在。

綜上,引理2.1得證。

引理2.2設(shè)m≥1,則γt2(Hm)+4≤γt2(Hm+3)。

證明設(shè)D是Hm+3的一個(gè)最小半全控制集,即|D|=γt2(Hm+3)。由引理2.1知|D∩(Yn+1∪Yn+2∪Yn+3∪Yn+4∪Yn+5∪Yn+6)|≥4。

當(dāng)|D∩(Yn+1∪Yn+2∪Yn+3∪Yn+4∪Yn+5∪Yn+6)|=4時(shí),D∩Hm是Hm的一個(gè)半全控制集,此時(shí)γt2(Hm)≤γt2(Hm+3)-4。

當(dāng)|D∩(Yn+1∪Yn+2∪Yn+3∪Yn+4∪Yn+5∪Yn+6)|=5時(shí),若D∩(Yn∪Yn-1)≠?,令D′=(D∩Hm)∪{xn,k|xn-1,3-k∈D或xn,3-k∈D,k=1,2},則D′是Hm的半全控制集,有γt2(Hm)≤|D′|≤|D|-4=γt2(Hm+3)-4,引理得證。若D∩(Yn∪Yn-1)=?,則|D∩Yn-2|=2,令D′=(D∩Hm)∪{xn,1},易見D′是Hm的半全控制集,所以γt2(Hm)≤|D′|≤|D|-4=γt2(Hm+3)-4。

當(dāng)|D∩(Yn+1∪Yn+2∪Yn+3∪Yn+4∪Yn+5∪Yn+6)|≥6時(shí),令D′=(D∩Hm)∪{xn,1,xn,2},則D′是Hm的一個(gè)半全控制集,所以

γt2(Hm)≤|D′|≤|D|-4=γt2(Hm+3)-4。

因此,引理2.2得證。

由于H1?C6,所以有γt2(H1)=γt2(C6)=3[1]。下面我們考慮H2和H3的半全控制數(shù)。

引理2.3γt2(H2)=4。

證明由于{x2,1,x2,2,x4,1,x4,2}是H2的一個(gè)半全控制集,所以γt2(H2)≤4。接下來證明γt2(H2)≥4。

反證法,假設(shè)D是H2的一個(gè)半全控制集且|D|≤3。由于N[x2,1]、N[x2,2]、N[x4,1]和N[x4,2]這四個(gè)閉鄰域均含有D中的點(diǎn),則|D∩(N[x2,1]∪N[x4,1])|=1或|D∩(N[x2,2]∪N[x4,2])|=1。不妨設(shè)|D∩(N[x2,1]∪N[x4,1])|=1,即x3,1∈D。

為了控制x1,1和x5,1,在N[x2,2]和N[x4,2]中分別有x1,2∈D、x5,2∈D。但此時(shí)在D中都沒有與D中的三個(gè)點(diǎn)距離小于等于2的點(diǎn),與D是半全控制集矛盾。從而γt2(H2)≥4。

所以γt2(H2)=4,引理2.3得證。

引理2.4γt2(H3)=6。

證明{x2,1,x2,2,x4,1,x4,2,x6,1,x6,2}是H3的一個(gè)半全控制集,所以γt2(H3)≤6。下面證明γt2(H3)≥6。

反證法,假設(shè)D是H3的一個(gè)半全控制集且|D|≤5。所以有|D∩(N[x2,1]∪N[x4,1])|=1或|D∩(N[x2,2]∪N[x4,2])|=1或|D∩(N[x4,1]∪N[x6,1])|=1或|D∩(N[x4,2]∪N[x6,2])|=1。

由對稱性,不妨設(shè)|D∩(N[x2,1]∪N[x4,1])|=1,即x3,1∈D。為了控制x1,1,在N[x2,2]中有x1,2∈D,且|D∩(Y1∪Y2∪Y3)|≥3來保證D中存在與x1,2的距離小于等于2的點(diǎn)。由于N[x6,1]∩N[x6,2]=?,所以|D∩(Y1∪Y2∪Y3)|=3,|D∩Y4|=0,|D∩N[x6,1]|=|D∩N[x6,2]|=1。

若x5,2∈D,為了控制x6,1、x7,1和x7,2,有x7,1∈D,但此時(shí)D中沒有與x7,1距離小于等于2的點(diǎn),與D是半全控制集矛盾,所以x5,2?D。同理x5,1?D,此時(shí)|D∩Y6|=2,但D中沒有與x6,1、x6,2距離小于等于2的點(diǎn),這與D是半全控制集矛盾。從而γt2(H3)≥6。

所以γt2(H3)=6,引理2.3得證。

證明用歸納法證明。當(dāng)m=1,2,3時(shí)由引理2.3和引理2.4知引理結(jié)論正確。

證明設(shè)S={xi,1,xi+1,2|i≡1(mod 3),i+1≤n=2m+1}。

令

D={S∪{xn,1},m≡1(mod 3);

S,m≡2(mod 3);

S∪{xn,2},m≡0(mod 3).

由引理2.5和引理2.6,可得本文主要定理如下。

圖5給出了H4、H5和H6的一個(gè)半全控制集。

圖5 圖H4、H5、H6的半全控制集,其中著白色的頂點(diǎn)為半全控制點(diǎn)Figure 5 Graph H4, H5, H6 where white vertices are semitotal dominating vertices

3 結(jié) 語