特定雙羅馬控制數的刻畫

張 寧，葉淼林，張子杰

（安慶師范大學 數理學院,安徽安慶 246133）

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

在此基礎上，本文繼續對圖的雙羅馬進行討論。首先從雙羅馬控制數和最大度之間的關系出發，給出圖G是連通的一個必要條件，其次結合樹和塊圖所具有的特殊結構性質，刻畫得出特定雙羅馬控制數的相關結論。

1 預備知識

設G=(V(G),E(G))是一個圖，V(G)是圖G的頂點集，E(G)是圖G的邊集，階數n(G)=|V(G)|，邊數m(G)=|E(G)|。對于任意的v∈V(G)，v的開鄰域指v的所有鄰點構成的集合，即N(v)={u|uv∈E(G)}，閉鄰域N[v]=N(v)?{v}，記ˉ[v]=V(G)-N[v]。頂點v的度指與v相鄰的點的個數，即deg(v)=|N(v)|，記作d G(v)，Δ(G)表示圖G的最大度，δ(G)表示圖G的最小度。對于集合S?V(G),定義集合的開鄰域為集合的閉鄰域為N[S]=N(S)?S，G[S]表示由頂點集S導出的子圖，即刪去V(G)-S的所有點及與之關聯的所有邊。……