ワグナーグラフ

ワグナーグラフ
ワグナーグラフ
名前の由来	クラウス・ワーグナー
頂点	8
エッジ	12
半径	2
直径	2
胴回り	4
自己同型	16 ( D 8 )
彩度数	3
色指数	3
属	1
スペクトラム	${\displaystyle {\begin{pmatrix}3&1&{\sqrt {2}}-1&-1&-{\sqrt {2}}-1\\1&2&2&1&2\end{pmatrix}}}$
プロパティ	3次 ハミルトニアン 三角形のない 頂点推移 トロイダル 頂点
表記	男性8
グラフとパラメータの表

数学のグラフ理論の分野において、ワグナーグラフは8つの頂点と12の辺を持つ3正則グラフである。 ^[1]これは8頂点のメビウスラダーグラフである。

メビウスの梯子として、ワグナーグラフは非平面グラフですが、交差数が1 であるため頂点グラフになります。また、トーラスや射影平面に交差なしで埋め込むことができるため、トロイダルグラフでもあります。内周 4、直径 2、半径 2、彩色数3、彩色指数3 であり、3頂点接続かつ3辺接続されています。

ワグナーグラフには392本の全域木があり、これは完全二部グラフ K _3,3とともに、同じ頂点数を持つすべての立方グラフの中で最も多くの全域木を持っています。^[2]

ワグナーグラフは頂点推移グラフですが、辺推移グラフ ではありません。その完全自己同型群は、回転と反射の両方を含む八角形の対称性の群である、位数 16 の二面体群D ₈と同型です。

ワグナーグラフの 特性多項式は

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

これは、この特性多項式を持つ唯一のグラフであり、そのスペクトルによって決定されるグラフになります。

ワグナーグラフは三角形を持たず、独立数3を持ち、ラムゼー数 R (3,4) (任意のn頂点グラフに三角形または4頂点独立集合のいずれかが含まれる最小の数n )が9であることの証明の半分を提供します。 ^[3]

メビウス・ラダーはグラフマイナーの理論で重要な役割を果たしている。このタイプの最も初期の結果は、1937年のクラウス・ワグナーの定理（ワグナーの定理として知られる一連の結果の一部）であり、クリーク和演算を使用して平面グラフとメビウス・ラダーM _{8を組み合わせることで、} K ₅マイナーのないグラフを形成できるというものである。^[4]このため、M _{8 は}ワグナーグラフと呼ばれている。

ワグナーグラフは、木幅が最大 3 のグラフに対する4 つの極小禁制マイナーの 1 つでもあります (他の 3 つは、完全グラフK _{5 、}正八面体のグラフ、五角柱のグラフです)。また、枝幅が最大 3 のグラフに対する 4 つの極小禁制マイナーの 1 つでもあります (他の 3 つは、 K ₅、正八面体のグラフ、立方体グラフです)。^{[5] [6]}

ワグナーグラフは、立方 ハミルトングラフであり、 LCF表記法[4] ⁸で定義できます。これは、頂点を循環的に配置でき、各頂点が位置の異なる他の頂点と接続される循環グラフの一種であるアンドラーシュファイグラフのインスタンスです。また、循環クリークK _8/3と同型です。

これは、位相的なメビウスの帯上に循環する 4 つの段を持つラダー グラフとして描くことができます。

• 
  ワグナーグラフの彩色数は3 です。
• 
  ワグナーグラフの色指数は 3です。
• 
  メビウスの帯に描かれたワグナーグラフ。

ウィキメディア・コモンズには、ワグナーグラフに関連するメディアがあります。