ムーアグラフ

数学における未解決の問題:

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

グラフ理論では、ムーアグラフは、その内周（最短のサイクル長）が直径（最も遠い2つの頂点間の距離）の2倍以上である正則グラフです。そのようなグラフの次数が $d$ で、その直径が $k$ である場合、その内周は $2$ $k$ $+ 1$ に等しくなければなりません。これは、次数 $d$ で直径 $k$ のグラフの場合、その頂点の数が

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

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

ムーアグラフ $G$ の別の同等の定義は、内周が $g = 2 k + 1$ であり、正確には $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠ん/グ⁠ ( m – n + 1)$ サイクルの長さ $g$ 、ここで $n$ と $mはそれぞれ$ $G$ の頂点と辺の数です。これらは、グラフの内周と同じ長さのサイクルの数に関して極値です。^[1]

ムーアグラフは、これらのグラフの記述と分類の問題を提起したエドワード・F・ムーアにちなんで、ホフマンとシングルトン (1960) によって命名されました。

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

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

ピーターセングラフをムーアグラフとして表現したもの。幅優先探索木はどれも $i$ $\geq 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 \leq$ $i$ $\leq$ $kには最大$ $d$ $($ $d$ $- 1)$ $i$ $-1$ 個の頂点が存在することができることがわかる。したがって、頂点の総数は最大で

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

Hoffman & Singleton (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 \leq i \leq k$ のどのレベルでも、少なくとも $d (d - 1) i$ 個の頂点が存在することが分かる。したがって、頂点の総数は少なくとも

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

ムーアグラフでは、頂点の数に関するこの制限は正確に満たされます。各ムーアグラフの内周はちょうど $2 k + 1$ です。つまり、頂点の数が足りないため内周が大きくなり、サイクルが短くなると、幅優先探索ツリーの最初の $kレベルの頂点の数が少なすぎます。したがって、どのムーアグラフも、最小次数$ $d$ と内周 $2 k + 1 を$ 持つすべてのグラフの中で、頂点の数が最小になります。つまり、ケージです。

$内周が2 k$ の場合でも、同様に1辺の中点から幅優先探索木を形成できる。この内周で最小次数 $d$ のグラフの頂点数の最小境界は、

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である。ムーアグラフは以下の通りである。^[3]

$n$ $> 2$ ノード上の完全グラフ K $n ($ 直径 1、内周 3、次数 $n$ $- 1$ 、位数 $n$ )
奇数周期 $C 2 n +1$ （直径 $n$ 、胴回り $2 n + 1$ 、次数 2、位数 $2 n + 1$ ）
ピーターセングラフ（直径 2、胴回り 5、次数 3、順序 10）
ホフマン・シングルトングラフ（直径 2、胴回り 5、次数 7、位数 50）
直径2、内周5、次数57、位数3250の仮想グラフ（または複数のグラフ）。その存在は知られておらず、グラフ理論における最も有名な未解決問題の一つである。 ^[4]

既知のムーアグラフはすべて頂点推移グラフであるが、未知のグラフ（存在する場合）は自己同型群の位数が最大375であり、頂点数よりも少ないため、頂点推移グラフにはなり得ない。^[5]

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

参照

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

注記

^ Azarija & Klavžar (2015).
^ ab エルデシュ、レンイ、ソス (1966)。
^ Bollobás (1998)、定理19、p.276。
^ ダルフォ（2019年）。
^ Macaj & Širáň (2010).
^ 坂内＆伊藤 (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-04-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 研究開発ジャーナル、5 (4): 497–504、doi :10.1147/rd.45.0497、MR 0140437
マチャイ、マーティン、シラーニ、ヨゼフ (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にて。

[FOOTNOTEAzarijaKlavžar2015-1] Azarija & Klavžar (2015).

[FOOTNOTEErdősRényiSós1966-2] エルデシュ、レンイ、ソス (1966)。

[FOOTNOTEBollobás1998Theorem_19,_p._276-3] Bollobás (1998)、定理19、p.276。

[FOOTNOTEDalfó2019-4] ダルフォ（2019年）。

[FOOTNOTEMačajŠiráň2010-5] Macaj & Širáň (2010).

[6] 坂内＆伊藤 (1973);ダメレル (1973)