兩個(gè)圈笛卡爾乘積的羅馬控制數(shù)

胡夫濤，于紫嫣，孫美鈺

安徽大學(xué)數(shù)學(xué)科學(xué)學(xué)院，安徽 合肥 230601

圖的控制數(shù)的研究歷史可追溯到公元1850年。圖的控制問(wèn)題和相關(guān)子集問(wèn)題的研究是圖論研究中心熱點(diǎn)，引起了人們廣泛的研究，相關(guān)研究成果詳見(jiàn)專(zhuān)著[2-5]。在圖的控制論中，圖的羅馬控制數(shù)問(wèn)題是一個(gè)基本問(wèn)題，并且具有數(shù)學(xué)和歷史的雙重意義。REVELLE[6]在1997年介紹了羅馬控制問(wèn)題；IANSTEWART[7]在1999年討論了君士坦丁為保衛(wèi)羅馬帝國(guó)而采取的策略，并提出一個(gè)新的控制數(shù)，即羅馬控制數(shù)；COCKAYNE等[8]給出了圖中羅馬控制的定義；此外，還有很多的羅馬控制相關(guān)結(jié)果，例如文獻(xiàn)[9，10]。圖論研究中染色問(wèn)題研究(文獻(xiàn)[11])和圖的控制有很相似的地方，圖論研究也有很多重要的應(yīng)用[12]。

2個(gè)圖的笛卡爾乘積是構(gòu)造大的圖模型的重要工具。人們對(duì)常見(jiàn)的網(wǎng)絡(luò)，如路和路、路和圈、圈和圈的笛卡爾乘積，都有很深入的研究，在圖的控制數(shù)方面有很多研究成果：文獻(xiàn)[13]研究了路和圈的笛卡爾乘積的成對(duì)控制數(shù)；文獻(xiàn)[14]研究了圈和圈的全控制數(shù)和成對(duì)控制數(shù)；文獻(xiàn)[15]給出了一個(gè)算法求解圈與圈笛卡爾乘積的羅馬控制數(shù)精確值。對(duì)正整數(shù)n≥3，筆者通過(guò)嚴(yán)格的理論證明確定了P2×Cn,C3×Cn,C4×Cn,C5×Cn的羅馬控制數(shù)精確值和G6,n的羅馬控制數(shù)上界。

1 基本性質(zhì)

引理 1[8]對(duì)任意圖G,γ(G)≤γR(G)≤2γ(G)。

引理3[8]設(shè)f=(V0,V1,V2)是任意γR-函數(shù)，則：

1)G[V1],V1的子圖最大度為1；

2)V1和V2在G中無(wú)邊；

3)V0中的點(diǎn)最多連接V1中2個(gè)點(diǎn)；

4)V2是G[V1∪V2]的一個(gè)控制集。

引理4[8]設(shè)G是階為n的連通圖，則γR(G)=γ(G)+1當(dāng)且僅當(dāng)V中一點(diǎn)v的度為n-γ(G)。引理5[8]任意圖G的階為n，最大度為Δ，則：

2 主要結(jié)果

設(shè)Cn和Pn分別表示為階為n的圈和路，且它們的頂點(diǎn)集記為：

V(Cn)=V(Pn)=[n]={1,2,…,n}

記Gm,n=Cm×Cn為2個(gè)圈Cm和Cn的笛卡爾乘積，設(shè)它們的頂點(diǎn)集為：

V(Cm×Cn)=V(Pm×Cn)={vi,j:1≤i≤m,1≤j≤n}

對(duì)任意j∈[n]，記：

2.1 P2×Cn的羅馬控制數(shù)精確值

定理1設(shè)正整數(shù)n≥3，則:

注：黑實(shí)心點(diǎn)函數(shù)值為2，空心點(diǎn)函數(shù)值為0。圖1 構(gòu)造的P2×C8的羅馬控制函數(shù)Fig.1 Constructed RDF of P2×C8

易見(jiàn)f=(V0,V1,V2)是P2×Cn的一個(gè)羅馬控制函數(shù)，其中V0=V(P2×Cn)(V1∪V2)。因此：

利用反證法，假設(shè)存在P2×Cn的一個(gè)γR-函數(shù)f=(V0,V1,V2)，使得γR(P2×Cn)=2|V2|+|V1|=n。因?yàn)閂2中的一個(gè)點(diǎn)最多控制3個(gè)V0中的點(diǎn)，所以4|V2|+|V1|≥V(P2×Cn)=2n，從而得到4|V2|=2n，且|V1|=0。因此每個(gè)V2中的點(diǎn)都與V0中的3個(gè)點(diǎn)鄰接，且V0中每個(gè)點(diǎn)只與V2中唯一一點(diǎn)鄰接。根據(jù)對(duì)稱(chēng)性，不妨設(shè)v1,1∈V2，則v2,3∈V2，對(duì)應(yīng)v1,5∈V2，如此下去總會(huì)得到v1,n∈V2或者v1,n與V2中2個(gè)點(diǎn)相鄰，得到矛盾。因此當(dāng)n≡1,2,3(mod 4)時(shí)，γR(P2×Cn)=n+1。

綜上，有：

2.2 G3,n的羅馬控制數(shù)精確值

注：黑實(shí)心點(diǎn)函數(shù)值為2，紅實(shí)心點(diǎn)函數(shù)值為1，空心點(diǎn)函數(shù)值為0。圖2 構(gòu)造的G3,8的羅馬控制函數(shù)Fig.2 Constructed RDF of G3,8

易見(jiàn)f=(V0,V1,V2)是G3,n的一個(gè)羅馬控制函數(shù)，其中V0=V(G3,n)(V1∪V2)。因此：

所以：

2.3 G4,n的羅馬控制數(shù)精確值

定理3設(shè)正整數(shù)n≥3，則γR(G4,n)=2n。

證明設(shè)：

V2={v1,i,v3,j:i=0(mod 2),j=1(mod 2),i,j∈[n]}V1=φV0=V(G4,n)(V1∪V2)

則易見(jiàn)f=(V0,V1,V2)是G4,n的一個(gè)γR-函數(shù)，從而γR(G4,n)≤2n。圖3為構(gòu)造的G4,8的羅馬控制函數(shù)。

注：黑實(shí)心函數(shù)值為2，空心點(diǎn)函數(shù)值為0圖3 構(gòu)造的G4,8的羅馬控制函數(shù)Fig.3 Constructed RDF of G4,8

圖4 |V2∩|=2且f(v2,i+1)=2時(shí)的重新賦值Fig.4 Reassign when |V2∩|=2 and f(v2,i+1)=2

所以：

γR(G4,n)=2n

2.4 G5,n的羅馬控制數(shù)精確值

性質(zhì)1設(shè)正整數(shù)n≥3和l≥1，則：

γR(G5l,n)=2ln,n≡0(mod 5)

γR(G5l,n)≤2ln+2l,n≡1,2,3,4(mod 5)

證明設(shè)：

v8,p,…,v5l-2,p,v1,q,v6,q,…,v5l-4,q:i≡1(mod 5),j=2(mod 5),k≡3(mod 5),p≡4(mod 5),q≡4(mod 5)}

注：黑實(shí)心點(diǎn)函數(shù)值為2，空心點(diǎn)函數(shù)值為0。圖5 構(gòu)造的G5,10的羅馬控制函數(shù)Fig.5 Constructed RDF of G5,10

因此：

定理4設(shè)正整數(shù)n≥3，則:

證明根據(jù)性質(zhì)1，有：

γR(G5,n)=2n，n≡0(mod 5)

γR(G5,n)≤2n+2，n≡1,2,3,4(mod 5)

因此只需考慮n?0(mod 5)的情形。

設(shè)f=(V0,V1,V2)為G5,n的所有γR-函數(shù)中|V1|數(shù)最小的，其中f=2|V2|+|V1|，根據(jù)定義：

V2={v4,i,v2,j,v5,k,v3,p,v1,q:i≡1(mod 5),j≡2(mod 5),k≡3(mod 5),p≡4(mod 5),q≡4(mod 5)}

當(dāng)n?0(mod 5)時(shí)，v1,n?V2，此時(shí)v1,1∈V0不與任何V2中的點(diǎn)相鄰，矛盾。

V2={v4,i,v2,j,v5,k,v3,p,v1,q:i≡1(mod 5),j≡2(mod 5),k≡3(mod 5),p≡4(mod 5),q≡4(mod 5)}

2.5 G6,n羅馬控制數(shù)上界

定理5設(shè)正整數(shù)n≥6，則:

證明設(shè)：

k≡3(mod 6),p≡4(mod 6),q≡5(mod 6),r≡0(mod 6)

注：黑實(shí)心點(diǎn)的函數(shù)值為2，空心點(diǎn)的函數(shù)值為0。圖6 構(gòu)造的G6,8的羅馬控制函數(shù)Fig.6 Constructed RDF of G6,8

G6,n的羅馬控制數(shù)上界是可以達(dá)到的，因?yàn)槔锩嫔婕暗那闆r非常多，在以后的研究中將進(jìn)一步考慮其它Gm,n未確定的羅馬控制數(shù)。