指示された支配ゲーム

支配ゲームの成功と、指示された彩色ゲームという彩色ゲームの変種に触発されて、私たちは指示された支配ゲームと呼ばれる支配ゲームのバージョンを導入します。このゲームは任意のグラフG上で、二人のプレイヤー、支配者と妨害者によって行われます。支配者はできるだけ少ないラウンドでゲームを終了させたいと考え、一方で妨害者はその逆を望みます。各ラウンドにおいて、支配者は妨害者の以前の選択によってまだ支配されていないGの頂点uを指摘します。このルールにより、妨害者はuの閉じた近傍にある頂点を選ばざるを得ません。Gのすべての頂点が妨害者によって選ばれた頂点に支配されるとゲームは終了します。両方のプレイヤーが自らの目標に従って最適にプレイしていると仮定すると、ゲーム中に選ばれた頂点の数はGの指示された支配数γi(G)です。私たちは、他のグラフ不変量に関して表現された指示された支配数のいくつかの境界を証明します。特に、すべてのグラフGについてγi(G)≥Γ(G)であることを示すことにより、新しいグラフ不変量の位置をよく知られた支配チェーンで見つけ、指示された支配数がゲーム支配数や上限非冗長数とは比較できないことを示します。自明な上限境界γi(G)≤n(G)−δ(G)に関連して、n(G)≥2δ(G)+2を前提としたときに境界を達成するグラフGのクラスを特徴付けます。木、分割グラフ、グリッドにおいて、指示された支配数が独立数に等しいことを証明します。また、経路の累乗の指示された支配数の公式を見つけ、このことから、指示された支配数が上限非冗長数よりも任意に大きなグラフが存在することも導き出します。Gが立方体二部グラフであればγi(G)=n(G)/2であるという主張を支持する部分的な結果をいくつか示し、これをオープンな問題として残します。