マギーグラフのソースを表示

{{infobox graph
 | name = マギーグラフ
 | image = [[Image: McGee graph hamiltonian.svg|220px]]
 | namesake = W. F. McGee
 | vertices = 24
 | edges = 36
 | automorphisms = 32<ref name="Mathworld" />
 | girth = 7<ref name="Mathworld" />
 | diameter = 4<ref name="Mathworld" />
 | radius = 4
 | chromatic_number = 3<ref name="Mathworld" />
 | chromatic_index = 3<ref name="Mathworld" />
 | properties = [[立方体グラフ]]<br>[[ケージ_(グラフ理論)|ケージ]]<br>[[ハミルトングラフ]]
|book thickness=3|queue number=2}}

'''マギーグラフ'''とは、グラフ理論のグラフの1つであり、24頂点、36辺の、3-[[正則グラフ]]である<ref name="Mathworld">{{MathWorld|urlname=McGeeGraph|title=McGee Graph}}</ref>。'''(3-7)-ケージ''' とも呼ばれる。

マギーグラフは (3,7)-[[ケージ (グラフ理論)|ケージ]]の唯一の例であり、 [[内周_(グラフ理論)|内周]]が7である立方体グラフの最小の例である。また、立方体グラフかつケージで、[[ムーアグラフ]]ではない最小のグラフである。

Sachsがマギーグラフを最初に見つけたが、発表しなかった<ref>Kárteszi, F. "Piani finit ciclici come risoluzioni di un certo problemo di minimo." Boll. Un. Mat. Ital. 15, 522-528, 1960</ref>。その結果、1960年に発表したマギーにちなんで、このグラフはマギーグラフと名付けられた<ref>McGee, W. F. "A Minimal Cubic Graph of Girth Seven." Canad. Math. Bull. 3, 149-152, 1960</ref>。その後、1966年に{{仮リンク|ウィリアム・トーマス・タット|en|William Thomas Tutte}}により、マギーグラフは (3,7)-ケージの唯一の例であることが証明された<ref>Tutte, W. T. Connectivity in Graphs. Toronto, Ontario: University of Toronto Press, 1966</ref><ref>Wong, P. K. "Cages--A Survey." J. Graph Th. 6, 1-22, 1982</ref><ref>Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance Regular Graphs. New York: Springer-Verlag, p. 209, 1989</ref>。

マギーグラフは平面グラフにすると8箇所以上で交叉する。つまり、マギーグラフの{{仮リンク|交叉数_(グラフ理論)|en|crossing number (graph theory)}}は8である。交叉数が8となる最小な立方体グラフには5つの非同型なグラフがあり、マギーグラフはその1つである。一般化[[ピーターセングラフ]]（{{仮リンク|ナウルグラフ|en|Nauru graph}}）もその1つである{{nobr|''G''(12,5)}}<ref> {{Cite OEIS|1=A110507|2=Number of nodes in the smallest cubic graph with crossing number n}}</ref><ref>{{citation|last1=Pegg|first1=E. T.|authorlink=Ed Pegg, Jr.|last2=Exoo|first2=G.|title=Crossing number graphs|journal=Mathematica Journal|volume=11|year=2009|url=http://www.mathematica-journal.com/issue/v11i2/CrossingNumberGraphs.html}}.</ref>。

マギーグラフの{{仮リンク|距離 (グラフ理論)|en|distance (graph theory)|label=距離}}は 4、[[グラフ理論#距離と直径|直径]]は 4、[[グラフ彩色|彩色数]]は 3 、[[グラフ彩色#辺彩色|彩色指数]]は 3である。マギーグラフは 3-[[k-頂点連結グラフ|頂点連結グラフ]] であり 3-[[k-辺連結グラフ|辺連結グラフ]]である。 本型埋め込み((book embedding)の厚み(book thickness)は 3 であり、queue numberは 2である<ref>Jessica Wolz, ''Engineering Linear Layouts with SAT''. Master Thesis, University of Tübingen, 2018</ref>。

== 代数的性質 ==
マギーグラフの[[固有多項式|特性多項式]]は<math>x^3(x-3)(x-2)^3(x+1)^2(x+2)(x^2+x-4)(x^3+x^2-4x-2)^4</math>である。
マギーグラフの[[自己同型|自己同型群]]の[[位数_(群論)|位数]]は 32 であり、その頂点は[[群作用|推移的]]ではない。つまり、長さ8や16の2つの頂点[[群作用#軌道と等方部分群|軌道]]をもつ。マギーグラフは[[vertex-transitive graph]]ではない（頂点が推移的でない）最小の立方体グラフである<ref>Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 237, 1976.</ref>・

== ギャラリー ==
<gallery>
Image:McGee graph crossing number.svg|マギーグラフの交叉数は8
Image:McGee graph 3COL.svg |マギーグラフの彩色数は3
Image:McGee graph  3color edge.svg|マギーグラフの彩色指数は3である
Image:Acyclic_coloring.svg|マギーグラフの非循環彩色数は3である
Image:McGee graph.svg|マギーグラフの他の表現
</gallery>

== 注釈・出典 ==
{{reflist}}

{{DEFAULTSORT:まきいくらふ}}
[[Category:グラフ理論のグラフ]]
[[Category:数学に関する記事]]