特定雙羅馬控制數(shù)的刻畫

張 寧，葉淼林，張子杰

（安慶師范大學(xué) 數(shù)理學(xué)院,安徽安慶 246133）

控制數(shù)和控制集的概念最早是由Ore[1]提出的，根據(jù)羅馬帝國的統(tǒng)治歷史，Stewart[2]于1999年首次提出了羅馬控制的概念，經(jīng)過多年的討論和發(fā)展，Beeler[3]等人于2016年在此基礎(chǔ)上改進(jìn)了羅馬防御戰(zhàn)路，推廣到了雙羅馬控制函數(shù)，研究給出了連通圖的雙羅馬控制數(shù)的一個(gè)上界，引起了廣泛的關(guān)注。2017年，Ahangar[4]等人給出了路徑Pn，圈Cn的雙羅馬控制數(shù)的準(zhǔn)確值，證明了二部圖和弦圖的雙羅馬控制問題是NP完備的。2018年，陳優(yōu)[5]刻畫了幾類特殊圖的雙羅馬控制數(shù)，Yue[6]研究給定最小度的圖和直徑為2的圖，并用線性時(shí)間算法描述了協(xié)圖的雙羅馬控制數(shù)。2021年，杜良麗[6]討論得出了笛卡爾積運(yùn)算下，格子圖P2□Pm的雙羅馬控制數(shù)。2022年謝智紅[7]等人借用圍長、周長等圖論工具，給出含圈圖的雙羅馬控制數(shù)的若干界限。2023年Erovnik[8]總結(jié)了歷年來雙羅馬控制已有的結(jié)論，并給出一些公開的問題和猜想。

在此基礎(chǔ)上，本文繼續(xù)對圖的雙羅馬進(jìn)行討論。首先從雙羅馬控制數(shù)和最大度之間的關(guān)系出發(fā)，給出圖G是連通的一個(gè)必要條件，其次結(jié)合樹和塊圖所具有的特殊結(jié)構(gòu)性質(zhì)，刻畫得出特定雙羅馬控制數(shù)的相關(guān)結(jié)論。

1 預(yù)備知識

設(shè)G=(V(G),E(G))是一個(gè)圖，V(G)是圖G的頂點(diǎn)集，E(G)是圖G的邊集，階數(shù)n(G)=|V(G)|，邊數(shù)m(G)=|E(G)|。對于任意的v∈V(G)，v的開鄰域指v的所有鄰點(diǎn)構(gòu)成的集合，即N(v)={u|uv∈E(G)}，閉鄰域N[v]=N(v)?{v}，記ˉ[v]=V(G)-N[v]。頂點(diǎn)v的度指與v相鄰的點(diǎn)的個(gè)數(shù)，即deg(v)=|N(v)|，記作d G(v)，Δ(G)表示圖G的最大度，δ(G)表示圖G的最小度。對于集合S?V(G),定義集合的開鄰域?yàn)榧系拈]鄰域?yàn)镹[S]=N(S)?S，G[S]表示由頂點(diǎn)集S導(dǎo)出的子圖，即刪去V(G)-S的所有點(diǎn)及與之關(guān)聯(lián)的所有邊。如果圖G的分支ω(G)=1，則稱G是連通圖，否則稱G是不連通的。如果G只有一個(gè)頂點(diǎn)，則稱G是平凡圖，否則稱G是非平凡圖。Kn表示n階完全圖，Pn表示階數(shù)為n的路，Cn表示階數(shù)為n的圈，無圈的連通圖稱為樹。如果B?G，B沒有割點(diǎn)且真包含B的子圖至少有一個(gè)割點(diǎn)，則稱連通子圖B是塊，如果G的每個(gè)塊都是完全圖，則稱G是塊圖。設(shè)V(G)={u1,u2,…,up}，V(H)={v1,v2,…,vq}，定義兩個(gè)簡單圖G和H的笛卡爾積運(yùn)算：頂點(diǎn)集為V(G)×V(H)，邊集為所有形如(u1,v1)(u2,v2)的集合，滿足：v1=v2，u1u2∈E(G)或者u1=u2，v1v2∈E(H)，記作G□H。

接下來，定義本文涉及到的兩類控制以及各自對應(yīng)的控制數(shù)，并給出證明中所用到的引理。

定義1[3]對于S?V(G)，如果N[S]=V(G)，則稱頂點(diǎn)集S是圖G的一個(gè)控制集，控制集的最小基數(shù)稱為控制數(shù)，記作γ(G)，即γ(G)=min{|S||S是G的控制集}，圖G中，基數(shù)為γ(G)的控制集稱為G的γ(G)-集。

定義2[3]設(shè)函數(shù)f:V(G)→{0,1,2,3}，令={v∈V(G)|f(v)=i,i=0,1,2,3}，若f滿足條件：

（1）如果f(v)=0，則v至少有兩個(gè)鄰點(diǎn)在中或者v有一個(gè)鄰點(diǎn)在中；

（2）如果f(v)=1，則v至少有一個(gè)鄰點(diǎn)在中。

則稱f是圖G的雙羅馬控制函數(shù)，簡記為DRDF f。函數(shù)f:V(G)→{0,1,2,3}與頂點(diǎn)劃分=間存在一個(gè)一一對應(yīng)，可記作雙羅馬控制函數(shù)的權(quán)定義為所有頂點(diǎn)的賦值之和，即最小權(quán)稱為圖G的雙羅馬控制數(shù)，記作γdR(G)，即γd R(G)=min{ω(f)|f是G的雙羅馬控制函數(shù)}。圖G中，權(quán)為γdR(G)的雙羅馬控制函數(shù)稱為G的γdR(G)-函數(shù)。

引理1[3]在圖G的權(quán)為γdR(G)的雙羅馬控制函數(shù)中，一定存在γdR(G)-函數(shù)，沒有頂點(diǎn)賦值為1。

引理2[3]對任意的圖G，2γ(G)≤γdR(G)≤3γ(G)。

引理3[3]對任意的樹T，2γ(T)+1≤γdR(T)≤3γ(T)。

引理4[4]如果G是一個(gè)非平凡的塊圖，則γdR(G)≥2γ(G)+1。

引理5[5]設(shè)G是一個(gè)連通圖，是G的一個(gè)γdR(G)-函數(shù)，是G的γ(G)-集，則有下列性質(zhì)：

（a）是獨(dú)立集，與之間沒有邊；

（b）中任一點(diǎn)都與中的某點(diǎn)相鄰；

（c）若G是一個(gè)樹或塊圖，則中任意兩點(diǎn)都沒有公共鄰點(diǎn)，且中的任一點(diǎn)都和中的某點(diǎn)相鄰。

引理6[6]設(shè)G是n階圖，最大度為Δ(G)，則γdR(G)≤2n(G)-2Δ(G)+1。

2 主要結(jié)果

定理1設(shè)G是n階簡單圖，最小度δ(G)≥2，如果γdR(G)+2Δ(G)=2n(G)+1，則G是連通圖。

證明假設(shè)G不是連通圖，設(shè)G1,G2,…,Gk是G的k個(gè)分支，其頂點(diǎn)集分別為n(G1),n(G2),…,n(Gk)，不失一般性，令Δ(G)=Δ(Gk)，根據(jù)條件，有

由引理6知對于每個(gè)Gi，滿足γdR(Gi)≤2n(Gi)-2Δ(Gi)+1，又因?yàn)閷θ我獾膇有Δ(Gi)≥δ(Gi)≥2，從而

因此只能k=1，故G是連通圖。

下面給出滿足γdR(G)+2Δ(G)=2n(G)+1的n階連通圖G的一個(gè)性質(zhì)。

定理2設(shè)G是n階簡單圖，最大度為Δ(G)，如果γdR(G)+2Δ(G)=2n(G)+1，則對于每個(gè)最大度頂點(diǎn)v，有：

（1）N(v)的每個(gè)頂點(diǎn)至多和Nˉ[v]中的一個(gè)頂點(diǎn)相鄰；

（2）G[[v]]是無邊圖。

證明令v是V(G)中一個(gè)度最大的頂點(diǎn)，即Δ(G)=deg(v)?？紤]圖G的雙羅馬控制函數(shù)f，使得

計(jì)算上述定義的DRDF,f的權(quán)，即

此時(shí)，γdR(G)=ω(f)，因此我們構(gòu)造的f是圖G的γdR(G)-函數(shù)。

（1）記w是v的一個(gè)鄰點(diǎn)，利用反證法，假設(shè)w至少與[v]中的兩個(gè)頂點(diǎn)相鄰，即N(w)?[v]≥2，重新定義一個(gè)函數(shù)g，使得：

根據(jù)雙羅馬控制函數(shù)的定義，上述定義的函數(shù)g是一個(gè)DRDF，g的權(quán)

這樣，找到了一個(gè)權(quán)比f小的DRDF,g與f是圖G的γdR(G)-函數(shù)矛盾，因此，N(v)的每個(gè)頂點(diǎn)至多和ˉ[v]中的一個(gè)頂點(diǎn)相鄰。

（2）如果u∈ˉ[v]有一個(gè)鄰點(diǎn)在[v]中，記作w。定義函數(shù)h，使得：

按上述構(gòu)造的函數(shù)h滿足DRDF的定義，且h的權(quán)

通過計(jì)算，說明h的權(quán)比f的權(quán)小，與f的權(quán)是最小的矛盾，故ˉ[v]中任意兩點(diǎn)都不相鄰，即G[[v]]是無邊圖。

定理3如果G是n階樹或非平凡的塊圖，是圖G的γdR(G)-函數(shù)，是G的γ(G)-集，則γdR(G)=2γ(G)+1當(dāng)且僅當(dāng)存在一個(gè)度為n(G)-γ(G)的頂點(diǎn)。

證明充分性

假設(shè)G有一個(gè)頂點(diǎn)v，deg(v)=n(G)-γ(G)，若是G的一個(gè)DRDF函數(shù)，令

計(jì)算得出g的權(quán)

由引理3和引理4知，對于樹或者非平凡的塊圖G，有2γ(G)+1≤γdR(G)=ω(f)≤ω(g)=2γ(G)+1，從而γdR(G)=2γ(G)+1。

必要性

此時(shí)定義的函數(shù)g符合雙羅馬控制函數(shù)的定義，則g的權(quán)

得到一個(gè)權(quán)比f小的雙羅馬控制函數(shù)g，與f是γdR(G)-函數(shù)矛盾，所以中任意兩點(diǎn)都不相鄰。又因?yàn)镚中沒有連接{v}與的邊，由引理5（c）知因此deg(v)==n(G)-γ(G)。

定理4如果G是n階樹或非平凡的塊圖，是G的一個(gè)γdR(G)-函數(shù)，是G的γ(G)-集，則γdR(G)=2γ(G)+2當(dāng)且僅當(dāng)

（1）G中沒有度為n(G)-γ(G)的頂點(diǎn)；

（2）G有兩個(gè)頂點(diǎn)v和w，使得|N[v]?N[w]|=n(G)-γ(G)+2。

證明充分性

因?yàn)镚沒有度為n(G)-γ(G)的頂點(diǎn)，所以由引理3，引理4，定理3知γdR(G)>2γ(G)+1，如果G有兩個(gè)頂點(diǎn)v和w，使得|N[v]?N[w]|=n(G)-γ(G)+2，重新構(gòu)造DRDF g=，使得：

則雙羅馬控制函數(shù)g的權(quán)

所以2γ(G)+1<γdR(G)=ω(f)≤ω(g)=2γ(G)+2，故γdR(G)=2γ(G)+2。

必要性

對于一個(gè)γdR(G)-函數(shù)f=且γdR(G)=2γ(G)+2，是G的γ(G)-集，滿足等式組：

（2）G中存在一個(gè)k個(gè)頂點(diǎn)的集合Wk使得=n(G)-γ(G)+k。

證明必要性

設(shè)f=是G的γdR(G)-函數(shù)，權(quán)為2γ(G)+k，即=2γ(G)+k。

首先證明（1）。

假設(shè)結(jié)論不成立，即存在整數(shù)t0，有1≤t0≤k-1，且G存在一個(gè)t0個(gè)頂點(diǎn)的集合使得=n(G)-γ(G)+t0，由定理3知t0≥2（否則，若t0=1，則γdR(G)=2γ(G)+1，與條件γdR(G)=2γ(G)+k矛盾，這里k≥2）。設(shè)DRDFf′=其中

根據(jù)雙羅馬控制函數(shù)的定義和定理?xiàng)l件，有

另一方面，假設(shè)γdR(G)=2γ(G)+m，其中m≥k+1，即2≤k≤m-1，由必要性（1）知G中不存在t（1≤t≤m-1）個(gè)頂點(diǎn)的集合Ut使得=n(G)-γ(G)+t，這與條件（2）G中存在k（2≤k≤m-1）個(gè)頂點(diǎn)的集合Wk使得=n(G)-γ(G)+k矛盾。因此γdR(G)=2γ(G)+k。

3 結(jié) 論

控制數(shù)一直是圖論的經(jīng)典問題，其形式多種多樣。本文從連通圖的雙羅馬控制數(shù)出發(fā)，描述了最大度條件下給定雙羅馬控制數(shù)的圖所具有的性質(zhì)，給出判斷連通圖的必要條件。根據(jù)樹和塊圖的相關(guān)結(jié)論，研究得出γdR(G)=2γ(G)+k(1≤k≤γ(G))的充要條件，建立起雙羅馬控制數(shù)與控制數(shù)之間的關(guān)系，描繪出在此特定雙羅馬控制數(shù)下圖所具有的特點(diǎn)，拓展了n階樹或非平凡的塊圖的結(jié)構(gòu)，豐富了對雙羅馬控制數(shù)的研究。