グラフペブリング

グラフ ペブリングは、各頂点に 0 個以上の小石があるグラフ上で行われる数学ゲームです。「ゲーム プレイ」は、一連のペブリング ムーブで構成されます。グラフ上のペブリング ムーブは、少なくとも 2 個の小石がある頂点を選択し、そこから 2 個の小石を取り除き、隣接する頂点に 1 個追加する (2 番目に取り除いた小石はゲームから除外されます) というものです。グラフGのペブリング数 π( G ) は、次の条件を満たす 最小の自然数nです。

グラフ内の任意のターゲット頂点または「ルート」頂点と、グラフ上のn 個の小石の任意の初期構成が与えられると、おそらく空の一連の小石移動の後に、指定されたルート頂点に 1 つ以上の小石がある新しい構成に到達する可能性があります。

たとえば、2 つの頂点とそれらを接続する 1 つの辺を持つグラフでは、ペブリング数は 2 です。2 つのペブルをグラフの頂点にどのように配置しても、選択した頂点にペブルを配置するという目的の結果に常に到達できます。最初の構成が頂点ごとに 1 つのペブルの構成である場合、ペブリング移動なしで目的が簡単に達成されます。グラフ ペブリングの中心的な問題の 1 つは、特定のグラフGの π( G ) の値です。

ペブリングに関するその他のトピックには、カバー ペブリング、最適ペブリング、支配カバー ペブリング、ペブリング数の境界としきい値、およびディープ グラフが含まれます。

ペブリングゲームの応用例の一つは、暗号におけるメモリ困難な関数のセキュリティ分析である。^[1]

ペブリングゲームは、数論における特定の問題を解くためのツールとして、ラガリアスとサックスによって最初に提案されました。1989年にFRKチョンが文献^[2]でこの概念を紹介し、ペブリング数π( G )を定義しました。

n頂点の完全グラフのペブリング数はnであることが簡単に確認できます。グラフにn  − 1 個のペブルを置くことができる場合、ターゲット以外の各頂点に 1 個ずつペブルを置くことができます。2 個以上のペブルを持つ頂点はないため、移動は不可能であり、ターゲットにペブルを置くことはできません。したがって、ペブリング数はn  − 1より大きくなければなりません。n 個のペブルがある場合、2 つのケースが考えられます。各頂点に 1 個のペブルがある場合、移動は必要ありません。いずれかの頂点が裸の場合、少なくとも他の 1 つの頂点に 2 個のペブルがあり、1 回のペブリング移動で完全グラフの任意のターゲット頂点にペブルを追加できます。^[2]

ペブリング数は、次のグラフ族で知られています。

• ${\displaystyle \pi (K_{n})=n}$はn頂点の完全グラフである。^[2]${\displaystyle K_{n}}$
• ${\displaystyle \pi (P_{n})=2^{n-1}}$はn頂点のパスグラフである。^[2]${\displaystyle P_{n}}$
• ${\displaystyle \pi (W_{n})=n}$、ここではn頂点のホイール グラフです。${\displaystyle W_{n}}$

チャン（1989）は、グラフの直積のペブリング数は最大でも因子のペブリング数の積に等しいという予想をロナルド・グラハムに与えた。 ^[3]これはグラハムのペブリング予想として知られるようになった。特殊なケースが知られているものの、未解決のままである。^[4]

Crullらは被覆ペブリングの概念を導入した。グラフGの被覆ペブリング数γ( G )は、一連のペブリング移動の後に、ペブリングの任意の初期配置からグラフが覆われるために必要な最小のペブリング数である。つまり、すべての頂点に少なくとも1つのペブリングがある。^[5]スタッキング定理と呼ばれる結果により、任意のグラフの被覆ペブリング数が求められる。^{[6] [7]}

積み重ね定理によれば、最も多くの小石を被覆解く必要がある小石の初期配置は、すべての小石が単一の頂点に配置されているときです。この観察に基づいて、次のように定義します。

${\displaystyle s(v)=\sum _{u\in V(G)}2^{d(u,v)}}$

Gのすべての頂点vに対して、d ( u , v ) はuからvまでの距離を表します。この場合、カバーペブリング数は結果として得られる最大のs ( v ) になります。

カバーペブリング数は、次のグラフのファミリで知られています。

• ${\displaystyle \gamma (K_{n})=2n-1}$、ここではn頂点の完全グラフです。${\displaystyle K_{n}}$
• ${\displaystyle \gamma (P_{n})=2^{n}-1}$、ここではn個の頂点を持つパス グラフです。${\displaystyle P_{n}}$
• ${\displaystyle \gamma (W_{n})=4n-9}$はn頂点のホイールグラフである。^[8]${\displaystyle W_{n}}$

• 小石ゲーム
• スペースの証明