マギーグラフ
マギーグラフとは、グラフ理論のグラフの1つであり、24頂点、36辺の、3-正則グラフである[1]。(3-7)-ケージ とも呼ばれる。
マギーグラフは (3,7)-ケージの唯一の例であり、 内周が7である立方体グラフの最小の例である。また、立方体グラフかつケージで、ムーアグラフではない最小のグラフである。
Sachsがマギーグラフを最初に見つけたが、発表しなかった[2]。その結果、1960年に発表したマギーにちなんで、このグラフはマギーグラフと名付けられた[3]。その後、1966年にテンプレート:仮リンクにより、マギーグラフは (3,7)-ケージの唯一の例であることが証明された[4][5][6]。
マギーグラフは平面グラフにすると8箇所以上で交叉する。つまり、マギーグラフのテンプレート:仮リンクは8である。交叉数が8となる最小な立方体グラフには5つの非同型なグラフがあり、マギーグラフはその1つである。一般化ピーターセングラフ（テンプレート:仮リンク）もその1つであるテンプレート:Nobr[7][8]。
マギーグラフのテンプレート:仮リンクは 4、直径は 4、彩色数は 3 、彩色指数は 3である。マギーグラフは 3-頂点連結グラフ であり 3-辺連結グラフである。 本型埋め込み((book embedding)の厚み(book thickness)は 3 であり、queue numberは 2である[9]。
代数的性質
マギーグラフの特性多項式はである。 マギーグラフの自己同型群の位数は 32 であり、その頂点は推移的ではない。つまり、長さ8や16の2つの頂点軌道をもつ。マギーグラフはvertex-transitive graphではない（頂点が推移的でない）最小の立方体グラフである[10]・
ギャラリー
-
マギーグラフの交叉数は8 -
マギーグラフの彩色数は3 -
マギーグラフの彩色指数は3である -
マギーグラフの非循環彩色数は3である -
マギーグラフの他の表現
注釈・出典
- ↑ テンプレート:MathWorld
- ↑ Kárteszi, F. "Piani finit ciclici come risoluzioni di un certo problemo di minimo." Boll. Un. Mat. Ital. 15, 522-528, 1960
- ↑ McGee, W. F. "A Minimal Cubic Graph of Girth Seven." Canad. Math. Bull. 3, 149-152, 1960
- ↑ Tutte, W. T. Connectivity in Graphs. Toronto, Ontario: University of Toronto Press, 1966
- ↑ Wong, P. K. "Cages--A Survey." J. Graph Th. 6, 1-22, 1982
- ↑ Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance Regular Graphs. New York: Springer-Verlag, p. 209, 1989
- ↑ テンプレート:Cite OEIS
- ↑ テンプレート:Citation.
- ↑ Jessica Wolz, Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018
- ↑ Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 237, 1976.