ムーアグラフ

数学における未解決問題

内周 5、次数 57 のムーアグラフは存在するでしょうか?

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

グラフ理論において、ムーアグラフとは、その内周（最短の閉路長）が直径（最も遠い2つの頂点間の距離）の2倍以上である正則グラフのことである。このようなグラフの次数がdで直径がkの場合、その内周は2 k + 1に等しくなければならない。これは、次数dで直径kのグラフにおいて、その頂点数（次数）が2 k + 1に等しい場合にのみ成り立つ。

${\displaystyle 1+d\sum _{i=0}^{k-1}(d-1)^{i},}$

この次数と直径を持つグラフにおける、頂点の最大数の上限。したがって、これらのグラフは、そのパラメータに対して次数直径問題を解く。

ムーアグラフGの別の同等の定義は、内周がg = 2 k + 1であり、正確には⁠n/グラム⁠ ( m − n + 1)個の長さgの閉路が、ここでnとmはそれぞれグラフGの頂点数と辺数である。これらは、グラフの内周の長さに相当する閉路の数に関して極値となる。 ^{[ 1 ]}

ムーアグラフは、これらのグラフの記述と分類に関する問題を提起したエドワード・F・ムーアにちなんで、ホフマンとシングルトン（1960）によって命名されました。ホフマンとシングルトンは、直径が2の場合、次数は2、3、7、または57のいずれかであることを示しました（これらのグラフはすべて強正則です）。また、直径が3の場合、Gは7サイクルでなければならないことも示しました。その後、ダメレル（1973）は、奇数サイクルを除いて、直径が2を超えるムーアグラフは存在しないことを証明しました。

ムーアグラフは、与えられた次数と直径の組み合わせに対して可能な頂点数が最大であるだけでなく、与えられた次数と内周を持つ正則グラフに対して可能な頂点数が最小である。つまり、任意のムーアグラフはケージである。^{[ 2 ]}ムーアグラフの頂点数の公式は一般化することができ、内周が奇数であるムーアグラフだけでなく、偶数であるムーアグラフも定義することができ、これらのグラフもケージである。

次数と直径による頂点の境界設定

ピーターセングラフをムーアグラフとして表現したもの。任意の幅優先探索木は、i ≥ 1のi番目のレベルにd ( d − 1) ^{i −1}個の頂点を持つ。

Gを最大次数d、直径kの任意のグラフとし、任意の頂点vから始まる幅優先探索によって形成される木を考える。この木はレベル 0 ( v自身) に 1 個の頂点を持ち、レベル 1 ( vの隣接頂点) には最大でd 個の頂点を持つ。次のレベルには最大でd ( d − 1)個の頂点がある。つまり、 vの各隣接頂点は、その隣接関係の 1 つを使用してvに接続するため、レベル 2 には最大でd − 1 個の隣接頂点を持つことができる。一般に、同様の議論から、任意のレベル1 ≤ i ≤ kには最大でd ( d − 1) ^{i −1}個の頂点が存在することができる。したがって、頂点の総数は最大で

${\displaystyle 1+d\sum _{i=0}^{k-1}(d-1)^{i}.}$

ホフマンとシングルトン（1960）は、この頂点数の上界が厳密に満たされるグラフをムーアグラフと定義しました。したがって、任意のムーアグラフは、最大次数dと最大直径kを持つすべてのグラフの中で、頂点数が最大となります。

その後、シングルトン (1968)は、ムーア グラフは直径kと内周2 k + 1を持つものとして定義できることを示しました。この 2 つの要件を組み合わせることで、グラフはあるdに対してd正則になり、頂点カウントの公式を満たすようになります。

ムーアグラフをケージとして

グラフの最大次数と直径で頂点の数の上限を決める代わりに、同様の方法で最小次数と内周で頂点の数の下限を計算することができる。^{[ 2 ]} Gの最小次数がdで内周が2 k + 1だとする。開始頂点vを任意に選択し、前と同様にvをルートとする幅優先探索木を考える。この木はレベル 0 ( v自身)に 1 つの頂点、レベル 1 に少なくともd個の頂点を持つ必要がある。レベル 2 ( k > 1の場合) では、少なくともd ( d − 1)個の頂点が必要であり、これはレベル 1 の各頂点には少なくともd − 1 個の隣接関係が残っており、レベル 1 の 2 つの頂点が互いに隣接したり、レベル 2 の共有頂点と隣接したりすることはできないためである。一般に、同様の議論から、1 ≤ i ≤ kのどのレベルでも、少なくともd ( d − 1) ⁱ個の頂点が存在することがわかる。したがって、頂点の総数は少なくとも

${\displaystyle 1+d\sum _{i=1}^{k-1}(d-1)^{i}.}$

ムーアグラフでは、頂点数に関するこの上限は厳密に満たされます。各ムーアグラフの内周はちょうど2 k + 1です。つまり、内周を大きくするには頂点数が足りず、閉路を短くすると、幅優先探索木の最初のkレベルの頂点数が少なすぎることになります。したがって、任意のムーアグラフは、次数dが最小で内周が2 k + 1であるすべてのグラフの中で、頂点数が最小となります。つまり、ケージです 。

内周が2 kの偶数グラフの場合、同様に、単一の辺の中点から始まる幅優先探索木を構成できる。この内周で次数が最小のグラフにおける頂点数の最小上限は、以下の通りである。

${\displaystyle 2\sum _{i=0}^{k-1}(d-1)^{i}=1+(d-1)^{k-1}+d\sum _{i=0}^{k-2}(d-1)^{i}.}$

（式の右辺は、単一の頂点から始まる幅優先探索木における頂点の数を数えるもので、木の最終レベルの頂点が前のレベルのd個の頂点に隣接する可能性を考慮しています。）したがって、ムーアグラフは、この境界を正確に満たすグラフを含むと定義されることがあります。繰り返しますが、そのようなグラフはすべてケージでなければなりません。

例

ホフマン・シングルトン定理によれば、内周が5のムーアグラフは次数が2、3、7、または57のいずれかである。ダメレルは、奇数サイクルを除いて直径が2を超えるムーアグラフは存在しないことを示した。したがって、ムーアグラフは以下の通りである。^{[ 3 ]}

• n > 2ノード上の完全グラフK _n（直径 1、内周 3、次数n − 1、位数n）
• 奇数閉路C _{2 n +1}（直径n、内周2 n + 1、次数 2、位数2 n + 1 ）。これには、直径 2、内周 5、次数 2、位数 5 のC ₅が含まれます。
• ピーターセングラフ（直径2、周囲長5、次数3、位数10）
• ホフマン・シングルトングラフ（直径2、内周5、次数7、位数50）
• 直径2、内周5、次数57、位数3250の仮想グラフ（または複数のグラフ）。このようなグラフの存在は知られておらず、グラフ理論における最も有名な未解決問題の一つである。 ^{[ 4 ]}

既知のムーアグラフはすべて頂点推移グラフであるが、57次のグラフは自己同型群の位数が最大375で頂点数より少ないため、頂点推移グラフにはならない。 ^{[ 5 ]}

偶数内周グラフを許容する一般化されたムーアグラフの定義を使用すると、偶数内周ムーアグラフは（退化している可能性のある）一般化多角形の接続グラフに対応する。例としては、偶数閉路C _{2 n}、完全二部グラフK _n、内周 4 の_n 、次数 3 で内周 6 のヒーウッドグラフ、次数 3 で内周 8 のタット・コクセターグラフなどがある。より一般的には、上に挙げたグラフを除いて、すべてのムーアグラフは内周 5、6、8、または 12 を持たなければならないことが知られている。^{[ 6 ]}偶数内周の場合は、一般化n角形のnの可能な値に関するフェイト・ヒグマン定理からも導かれる。

参照

• 与えられた直径と最大次数を持つ既知の最大グラフの表

注記

1. Azarija & Klavžar (2015) .
2. エルデシュ、レンイ、ソス (1966)。
3. Bollobás (1998)、定理19、p.276。
4. Dalfó (2019) .
5. Mačaj & Širáň (2010) .
6. 坂内・伊藤 (1973) ;ダメレル (1973)

参考文献

• Azarija, Jernej; Klavžar, Sandi (2015)、「ムーアグラフとサイクルは凸サイクルの極値グラフである」、Journal of Graph Theory、80 : 34–42、arXiv : 1210.6342、doi : 10.1002/jgt.21837、S2CID  333785
• 坂内 英之; 伊藤 毅 (1973) 「有限ムーアグラフについて」東京大学理学部紀要 第1章A 数学20 : 191– 208 , MR  0323615 、 2012年4月24日時点のオリジナルよりアーカイブ
• Bollobás, Béla (1998), Modern Graph Theory , Graduate Texts in Mathematics , vol. 184, Springer-Verlag。
• Dalfó, C. (2019)、「失われたムーアグラフに関する概観」(PDF)、線形代数とその応用、569 : 1– 14、doi : 10.1016/j.laa.2018.12.035、hdl : 2117/ 127212 、MR  3901732、S2CID  126689579
• Damerell, RM (1973)、「ムーアグラフについて」、ケンブリッジ哲学協会数学紀要、74 (2): 227– 236、Bibcode : 1973PCPS...74..227D、doi : 10.1017/S0305004100048015、MR  0318004
• ポール・エルデシュ; Rényi, アルフレッド; Sós、Vera T. (1966)、「グラフ理論の問題について」(PDF)、Studia Sci.数学。ハンガル。、1 : 215–235、オリジナル(PDF)から2016 年 3 月 9 日にアーカイブ、2010 年 2 月 23 日に取得。
• ホフマン、アラン・J. ; シングルトン、ロバート・R. (1960)、「直径2および3のムーアグラフ」、IBM Journal of Research and Development、5 (4): 497– 504、doi : 10.1147/rd.45.0497、MR  0140437
• Mačaj, Martin; Širáň, Jozef (2010)、「失われたムーアグラフの特性の探索」、線形代数とその応用、432 (9): 2381– 2398、doi : 10.1016/j.laa.2009.07.018。
• シングルトン、ロバート・R. (1968)、「不規則なムーアグラフは存在しない」、アメリカ数学月刊誌、75 (1): 42–43、doi : 10.2307/2315106、JSTOR  2315106、MR  0225679

外部リンク

• Brouwerと Haemers:グラフのスペクトル
• Weisstein, Eric W.、「ムーアグラフ」（「ホフマン-シングルトン定理」）、MathWorldにて。