ホフマングラフ

Hoffman_graph

グラフ理論の数学分野では、ホフマングラフは、アランホフマンによって発見された16個の頂点と32個のエッジを持つ4つの正則グラフです。 1963年に公開され、超立方体グラフQ4とコスペクトルです。
ホフマングラフ
ホフマングラフ
にちなんで名付けられた
アランホフマン
頂点 16 エッジ 32 半径 3 直径 4 胴回り 4 自己同型
48（Z / 2Z × S4）
色数 2 クロマチックインデックス 4 本の厚さ 3 キュー番号 2 プロパティ
ハミルトニアン2部パーフェクトオイラー
グラフとパラメータの表
ホフマングラフには、超立方体Q 4と多くの共通の特性がどちらもハミルトニアンであり、色数2、色指数4、周長4、直径4です。これは4頂点連結グラフと4辺連結グラフでも 。ただし、距離正則ではありません。ブックの厚さは3、キュー番号は2です。

代数的性質
ホフマングラフは頂点推移グラフではなく、その完全な自己同形群は、対称群S4と巡回群Z / 2Zの直積と同形の位数48の群です。
ホフマングラフの特性多項式は次のようになります。（（ X− 4 ）。 （（ X− 2
）。4X 6（（ X+ 2
）。 4 （（ X+ 4 ）。 {（x-4）（x-2）^ {4} x ^ {6}（x + 2）^ {4}（x + 4）}
  整数グラフ—スペクトルが完全に整数で構成されているグラフ。これは、超立方体Q4と同じスペクトルです。

ギャラリー

  ホフマングラフはハミルトニアンです。

  ホフマングラフの色数は2です。

  ホフマングラフの色指数は4です。

参考文献
^ ワイスタイン、エリックW. 「ハミルトングラフ」。MathWorld。
^ ワイスタイン、エリックW. 「ホフマングラフ」。MathWorld。
^ Hoffman、AJ「グラフの多項式について」。アメル。算数。月刊70、30-36、1963。
^ van Dam、ERおよびHaemers、WH「いくつかの距離正則グラフのスペクトル特性」。J.代数コンビン。15、189-202、2003。
^ Jessica Wolz、 SATを使用した線形レイアウトのエンジニアリング。テュービンゲン大学修士論文、2018年”