ホフマングラフ

グラフ理論の数学分野において、ホフマングラフは、アラン・ホフマンによって発見された、16個の頂点と32個の辺を持つ4正則グラフである。^{[ 2 ]} 1963年に発表されたこのグラフは、ハイパーキューブグラフQ4_とスペクトル的に一致する。^{[ 3 ] [ 4 ]}

ホフマングラフは、ハイパーキューブ Q ₄と多くの共通特性を持っています。どちらもハミルトングラフであり、彩色数2、彩色指数4、周長 4、直径 4 です。また、4頂点連結グラフであり、4辺連結グラフでもあります。ただし、距離正則ではなく、1 平面でもありません。^{[ 5 ]}ブックの厚さ は3、キュー数は2 です。^{[ 6 ]}

ホフマングラフは頂点推移グラフではなく、その完全自己同型群は、対称群S ₄と巡回群Z /2 Zの直積と同型な位数 48 の群です。頂点推移性も辺推移性もありませんが、ホフマングラフは依然として1-ウォーク正則です(ただし、距離正則ではありません)。

ホフマングラフの特性多項式は、

${\displaystyle (x-4)(x-2)^{4}x^{6}(x+2)^{4}(x+4)}$

これは整数グラフ、つまりスペクトルがすべて整数で構成されるグラフです。これは超立方体 Q ₄と同じスペクトルです。

• 
  ホフマングラフはハミルトニアンである。
• 
  ホフマングラフの彩色数 は2です。
• 
  ホフマングラフの彩色指数 は4です。