マクギーグラフ

マクギーグラフ
マクギーグラフ
にちなんで名付けられました	WFマギー
頂点	24
エッジ	36
半径	4
直径	4 [ 1 ]
周囲	7 [ 1 ]
自己同型写像	32 [ 1 ]
彩色数	3 [ 1 ]
色度指数	3 [ 1 ]
本の厚さ	3
順番待ち番号	2
不動産	立方体ケージハミルトニアン
グラフとパラメータの表

グラフ理論の数学分野では、マギーグラフまたは（3-7）ケージは、 24個の頂点と36個の辺を持つ3正則グラフである。^{[ 1 ]}

マギーグラフは、唯一の(3,7)ケージ（周長7の最小の立方体グラフ）です。また、ムーアグラフではない最小の立方体ケージでもあります。

最初にザックスによって発見されたが未発表であった^{[ 2 ]}このグラフは、1960年にその結果を発表したマクギーにちなんで名付けられた^{[ 3 ]。}その後、 1966年にタットによってマクギーグラフが唯一の(3,7)ケージであることが証明された^{[ 4 ] [ 5 ] [ 6 ]。}

マクギーグラフは、平面上に描画する際に少なくとも8つの交点を必要とします。これは、8つの交点を必要とする最小の3次グラフとして同数である3つの非同型グラフの1つです。これら3つのグラフのもう1つは、ナウルグラフとしても知られる一般化ピーターセングラフG (12,5)です。^{[ 7 ] [ 8 ]}

McGeeグラフは半径4、直径4、彩色数3、彩色指数3です。また、3頂点連結グラフ、3辺連結グラフでもあります。本の厚さは3、待ち行列数は2です。^{[ 9 ]} このグラフは1平面グラフです。^{[ 10 ]}

マクギーグラフの特性多項式は

${\displaystyle x^{3}(x-3)(x-2)^{3}(x+1)^{2}(x+2)(x^{2}+x-4)(x^{3}+x^{2}-4x-2)^{4}}$。

McGeeグラフの自己同型群は位数32であり、頂点に対して推移的に作用しない。長さ8と16の2つの頂点軌道が存在する。McGeeグラフは、頂点推移的グラフではない最小の立方体ケージである。^{[ 11 ]}

McGeeグラフの自己同型群、つまり対称群は32個の要素を持つ。この群は、すべてのアフィン変換の群と同型である。${\displaystyle \mathbb {Z} /8\mathbb {Z} }$すなわち、次の形式の変換

${\displaystyle x\mapsto ax+b}$

どこ${\displaystyle a,b\in \mathbb {Z} /8\mathbb {Z} }$そして${\displaystyle a}$は可逆なので、${\displaystyle a=1,3,5,7}$^{[ 12 ]} これは、考えられる最小の2つのグループのうちの1つです。${\displaystyle G}$すべての要素を写像する外部自己同型写像${\displaystyle g\in G}$共役な要素に${\displaystyle g}$[ ^{13 ]​}

• 
  マギーグラフの交点数 は8です。
• 
  マギーグラフの彩色数 は3です。
• 
  マギーグラフの彩色指数 は3です。
• 
  マギーグラフの非巡回彩色数 は3である。
• 
  マギーグラフの別図。