マギーグラフ
From Wikipedia, the free encyclopedia
マギーグラフとは、グラフ理論のグラフの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つであるG(12,5)[7][8]。
マギーグラフの距離は 4、直径は 4、彩色数は 3 、彩色指数は 3である。マギーグラフは 3-頂点連結グラフ であり 3-辺連結グラフである。 本型埋め込み((book embedding)の厚み(book thickness)は 3 であり、queue numberは 2である[9]。
