永遠の支配セット

グラフ上の永久支配集合の系列（青色で表示）です。赤色で表示され攻撃を行うには、青色の頂点（ガード）の1つが攻撃対象の頂点に移動する必要があります。ガードは攻撃のたびに移動することができ、グラフ上で支配集合であり続けることを保証します。このグラフ

の永久支配数γ _∞ ( G )は5です。これより小さいと、攻撃側がガードを敗北させる戦略をとらざるを得なくなります。これは、同じグラフの支配数 γ ( G )である4よりも大きいことに注意してください。

数学における未解決問題

γ ( G )がγ _∞ ( G )に等しく、 γ ( G )がGのクリーク被覆数より小さいようなグラフGは存在しますか？

数学におけるさらなる未解決問題

グラフ理論において、グラフG  = ( V ,  E )の永遠支配集合は、 VのサブセットDであり、Dは移動ガードが初期配置される支配集合である（どの頂点にも最大で 1 つのガードが配置できる）。集合Dは、頂点で連続して発生する任意の無限の攻撃シーケンスに対して、攻撃された頂点に攻撃時にガードがない場合、隣接する頂点から攻撃された頂点にガードを移動することによって集合Dを変更できるものでなければならない。各攻撃後のガードの構成によって、支配集合が誘導される必要がある。永遠支配数γ _∞ ( G )は、初期集合Dで可能な頂点の最小数である 。たとえば、5 つの頂点上のサイクルの永遠支配数は 3 である。

永遠支配集合問題（永遠支配問題、永遠安全問題とも呼ばれる）は、2人のプレイヤーが交互にターンを交代しながらプレイする組み合わせゲームとして解釈することもできます。防御側は、初期の支配集合Dと、ガードのない頂点への攻撃に送るガードを選択します。攻撃側は、自分のターンに攻撃する頂点を選択します。攻撃側は、攻撃する頂点として、その頂点または隣接する頂点にガードが存在しない頂点を選択できればゲームに勝利します。そうでない場合は防御側が勝利します。言い換えれば、攻撃側は、攻撃を防御できない頂点を攻撃できればゲームに勝利します。

Klostermeyer & Mynhardt (2015b) で指摘されているように、永遠支配集合問題はコンピュータ サイエンスにおける kサーバー問題に関連しています。

歴史

永遠支配問題は、Arquilla & Fredricksen (1995)、ReVelle & Rosing (2000)、Stewart (1999) の一連の論文で述べられた軍事防衛における古くからの問題に着想を得て、2004年にBurger et al. (2004) の論文で初めて提唱されました。その後、Goddard、Hedetniemi & Hedetniemi (2005) による永遠支配に関する論文が発表され、この問題のバリエーションとして「m -永遠支配」も提案されました。これは、攻撃を受けた頂点にガードが1人でも移動すれば、攻撃に応じてすべてのガードが必要に応じて隣接する頂点に移動できるというものです（攻撃を受けた頂点にガードがいないことを前提としています。そうでなければ、ガードは移動する必要はありません）。 Goddard、Hedetniemi & Hedetniemi (2005) の論文に続いて、数学文献には他の著者による多数の論文が発表されました。これらの後続論文では、永遠支配問題に関するいくつかのバリエーションが提案されました。これには、永遠頂点被覆問題、永遠独立集合問題、永遠全支配集合問題、永遠連結支配集合、そしてエビクションモデルにおける永遠支配集合（後者のモデルでは、攻撃発生時にガードを持つ頂点が存在し、ガードはガードを持たない隣接頂点（もし存在する場合）へ移動する必要がある）が含まれます。永遠支配問題に関する多くの結果とそのバリエーションを解説したサーベイ論文は、Klostermeyer & Mynhardt (2015b) に掲載されています。

境界

G をn ≥ 1 の頂点を持つグラフとします。 自明なことに、永遠支配数は少なくとも支配数 γ( G ) です。Goddard、Hedetniemi、および Hedetniemi は、論文の中で、永遠支配数は少なくともGの独立数であり、最大でもGのクリーク被覆数であることを証明しました ( Gのクリーク被覆数はGの補グラフの彩色数に等しい)。したがって、パーフェクトグラフ定理により、Gの永遠支配数はすべてのパーフェクトグラフに対してGのクリーク被覆数に等しくなります。G の永遠支配数は、円弧グラフ (Regan (2007) で証明)や直並列グラフ (Anderson ら (2007) で証明) など、他のいくつかのグラフクラスに対してもGのクリーク被覆数に等しいことが示されている。ゴダード、ヘデトニエミ、ヘデトニエミは、グラフの永遠支配数がクリーク被覆数よりも小さいグラフも実証しました。

Klostermeyer & MacGillivray (2007) は、独立数αを持つグラフの永遠支配数がほぼα ( α + 1)/2 であることを証明しました。Goldwasser & Klostermeyer (2008) は、永遠支配数がちょうどα ( α  + 1)/2  となるグラフが無限に存在することを証明しました。

境界のメートル-永遠の支配数

ゴダード、ヘデトニエミ、そしてヘデトニエミは、 m永遠支配数（γ ^m _∞ ( G ) と表記）が最大でGの独立数になることを証明した。したがって、永遠支配パラメータは、有名なパラメータの支配連鎖（Haynes, Hedetniemi & Slater 1998a 参照）に次のようにうまく適合する。

γ( G ) ≤ γ ^m _∞ ( G ) ≤ α( G ) ≤ γ _∞ ( G ) ≤ θ ( G )

ここで、_θ ( G )はGのクリーク被覆数、γ∞ ( G )は永遠支配数を表す。

n頂点のグラフのγ ^m _∞ ( G )上の⌈ n /2⌉の上限はChambers、Kinnersly、Prince (2006)で証明されています。KlostermeyerとMynhardt (2015b)も参照してください。

グリッドグラフにおけるm永遠支配数は、グリッドグラフの支配数に注目が集まっている。Haynes, Hedetniemi & Slater (1998a)およびGoncalves et al. (2011)を参照のこと。グリッドグラフにおけるm永遠支配数は、Goldwasser, Klostermeyer & Mynhardt (2013)で初めて研究され、以下のことが示された。

γ ^m _∞ = ⌈2 n /3⌉ 2行n列のグリッド（n  ≥ 2）の場合

そして

3行n列のグリッドの場合、 γ ^m _∞ ≤ ⌈8 n /9⌉ 。

後者はFinbow、Messinger、van Bommel（2015）で改良され、

1 + ⌈4 n /5⌉ ≤ γ ^m _∞ ≤ 2 + ⌈4 n /5⌉

n ≥ 11のとき、この境界はMessinger & Delaney (2015)でいくつかのケースで若干改善された。最終的にFinbow & van Bommel (2020)でこの境界は閉じられ、

γ ^m _∞ = ⌈(4 n +7)/5⌉（n  ≥ 22）です。

4 x n グリッドと 5 x nグリッドのケースは、それぞれ Beaton、Finbow、MacDonald (2013) と van Bommel、van Bommel (2016) で検討されました。

Braga、de Souza、Lee (2015) は、すべての適切な区間グラフについてγ ^m _∞ = αであることを証明しました。また、同じ著者らは、Goddard、Hedetniemi、Hedetniemi (2005) の主張に反して、 m永遠支配数が支配数と等しくないCayley グラフが存在することも証明しました(Braga、de Souza、Lee (2016) を参照) 。

未解決の質問

Klostermeyer & Mynhardt (2015b) によると、未解決の主な問題の 1 つは、γ ( G ) がGの永遠支配数に等しく、γ ( G ) がGのクリーク被覆数より小さいグラフGが存在するかどうかです。Klostermeyer & Mynhardt (2015a) は、このようなグラフには必ず三角形が含まれ、最大頂点次数が少なくとも 4 でなければならないことを証明しました。

支配集合に関するヴィジングの予想と同様に、すべてのグラフGとHについて、

${\displaystyle \gamma_{\infty}(G\,\Box\,H)\geq \gamma_{\infty}(G)\gamma_{\infty}(H).}$

Klostermeyer & Mynhardt (2015a) に示されているように、 m永遠支配問題 では、すべてのグラフGとHに対して同様の境界が成り立たないことが知られています。

ダグラス・ウェストは[1]において、永遠支配に関する2つの根本的な未解決問題を列挙している。すなわち、γ _∞ ( G ) はすべての平面グラフGのクリーク被覆数に等しいか、そしてγ _∞ ( G ) はロヴァース数（ロヴァース・シータ関数とも呼ばれる）によって下方に有界となるか、である。

他にも多くの未解決の質問が調査論文 Klostermeyer & Mynhardt (2015b) に記載されており、その中には前述の永遠支配集合のバリエーションに関する多くの質問が含まれています。

参考文献

• アンダーソン, M.; バリエントス, C.; ブリガム, R.; キャリントン, J.; ヴィトレー, R.; イエレン, J. (2007)「永久安全保障のための最大需要グラフ」, J. Combin. Math. Combin. Comput. , 61 : 111– 128。
• Arquilla, H.; Fredricksen, H. (1995)、「最適なグランド戦略のグラフ化」、Military Operations Research、1 (3): 3– 17、doi :10.5711/morj.1.3.3、hdl : 10945/38438、JSTOR  43940682。
• Beaton , I.; Finbow, S.; MacDonald, J. (2013)「グリッドの永遠支配集合問題」、J. Combin. Math. Combin. Comput.、85 : 33–38。
• Braga, A.; de Souza, C.; Lee, O. (2015)、「適切な区間グラフの永遠支配集合問題」、Information Processing Letters、115 ( 6–8 ): 582– 587、doi :10.1016/j.ipl.2015.02.004。
• Braga, A.; de Souza, C.; Lee, O. (2016)、「Goddard、Hedetniemi、Hedetniemi (2005)による論文「グラフにおける永久セキュリティ」に関する注記」、Journal of Combinatorial Mathematics and Combinatorial Computing、96 : 13– 22。
• バーガー、AP;コケイン、EJ。グランドリン、WR;ミンハルト、CM。ヴァン・ヴーレン、J. Winterbach、W. (2004)、「グラフにおける無限次数支配」、J. Combin.数学。組み合わせる。計算します。、50：179～ 194。
• Chambers, E.; Kinnersly, B.; Prince, N. (2006)、「Mobile permanent security in graphs」、未発表原稿、2015年9月30日アーカイブ、2015年2月21日取得。
• Finbow, S.; Messinger, ME.; van Bommel, M. (2015)「3 x n グリッドにおける永遠支配」Australas. J. Combin. , 61 : 156– 174。
• Finbow, S.; van Bommel, MF (2020)「3 xnグリッドグラフの永遠支配数」、Australas. J. Combin.、71 : 1– 23。
• ゴダード, ウェイン; ヘデトニエミ, サンドラ M.; ヘデトニエミ, スティーブン T. (2005年1月). 「グラフにおける永久セキュリティ」. Journal of Combinatorial Mathematics and Combinatorial Computing . 52 .
• Goldwasser, J.; Klostermeyer, W. (2008)、「グラフにおける永久支配集合の厳密な境界」、離散数学、308 (12): 2589– 2593、doi : 10.1016/j.disc.2007.06.005。
• Goldwasser, J.; Klostermeyer, W.; Mynhardt, C. (2013)「グリッドグラフにおける永久保護」、Utilitas Math.、91 : 47–64。
• Goncalves, D.; Pinlou, A.; Rao, M.; Thomasse, S. (2011)、「グリッドの支配数」、SIAM Journal on Discrete Mathematics、25 (3): 1443– 1453、arXiv : 1102.5206、doi :10.1137/11082574。
• ヘインズ、テレサ・W. ; ヘデトニエミ、スティーブン; スレーター、ピーター (1998a)、『グラフにおける支配の基礎』、マルセル・デッカー、ISBN 0-8247-0033-3、OCLC  37903553。
• Klostermeyer, W.; MacGillivray, G. ( 2007)、「固定独立数グラフにおける永久セキュリティ」、J. Combin. Math. Combin. Comput.、63 : 97–101。
• Klostermeyer, W.; Mynhardt, C. (2015a)、「支配、永遠支配、そしてクリーク被覆」、Discuss. Math. Graph Theory , 35 (2): 283, arXiv : 1407.5235 , doi :10.7151/dmgt.1799。
• Klostermeyer, W.; Mynhardt, C. (2015b)、「モバイルガードによるグラフの保護」、Applicable Analysis and Discrete Mathematics、10 :21、arXiv : 1407.5228、doi :10.2298/aadm151109021k。
• メッシンジャー、ME.; デラニー、A. (2015) 「ギャップを埋める：3 x n グリッドにおける永遠の支配」。
• Regan, F. (2007)、「グラフにおける支配と独立性の動的変種」、ライン・フリードリヒ・ヴィルレムス大学。
• ReVelle, C. (2007)、「ローマ帝国を守れるか？」Johns Hopkins Magazine、2。
• ReVelle, C.; Rosing, K. (2000)「ローマ帝国の防衛：軍事戦略における古典的問題」アメリカ数学月刊誌、107 (7): 585– 594、doi :10.2307/2589113、JSTOR  2589113。
• スチュワート, I. (1999)「ローマ帝国を守れ！」サイエンティフィック・アメリカン、281 (6): 136– 138、Bibcode :1999SciAm.281f.136S、doi :10.1038/scientificamerican1299-136。
• ファン・ボメル、C. van Bommel、M. (2016)、「5 xn グリッドの永遠の支配数」、J. Combin。数学。組み合わせる。コンピューティング、97 : 83–102。