車輪グラフ

ウィキペディア

車輪グラフ

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/07/30 05:55 UTC 版)

車輪グラフ
車輪グラフの例
頂点	n
辺	2(n - 1)
直径	1 (n = 4) 2 (n > 4)
内周	3
彩色数	3 （n が奇数の場合） 4 （n が偶数の場合）
特性	ハミルトングラフ 自己双対 平面グラフ
表記	Wn

車輪グラフ（しゃりんグラフ、英: Wheel graph）とは、グラフ理論のグラフの1つであり、閉路グラフと、そのすべての頂点に接続するユニバーサル頂点（支配頂点）と呼ばれる頂点からなるグラフである。n 頂点の車輪グラフは、 n - 1角錐の、1-骨格とも定義できる（3 < n)。n 頂点の車輪グラフをW_nで表したり、n + 1 頂点の車輪グラフを、 n 角形で表せることから W_nで表したりする。本記事内では、前者の表記を用いる。

内包表記での構成

頂点集合 {1, 2, 3, …, v }に対し辺の集合は内包表記で{{1, 2}, {1, 3}, …, {1, v}, {2, 3}, {3, 4}, …, {v - 1, v}, {v ,2}}と表せる。 ここで、頂点1がユニバーサル頂点であり、頂点2から頂点 v は閉路グラフを構成する。

性質

車輪グラフは

• 平面グラフであり、一意な平面グラフを持つ。
  • 車輪グラフはハリングラフ（木（グラフ）の葉を閉路でつないだ平面グラフ）である。
• 車輪グラフは自己双対である。
• 最大平面グラフは、K₄ = W₄であるか、W₅ か W₆を部分グラフとして含む。
• n - 1 種類のハミルトン閉路をもつ
• W_nに対して $n^{2}-3n+3$
  車輪グラフW₄に含まれる7種類の閉路。
  下3つはすべての頂点を通るため、ハミルトン閉路である。

  n が奇数の場合、 W_n は彩色数3のパーフェクトグラフである。つまり、ユニバーサル頂点以外の頂点を交互に2色に塗り分け、中央のユニバーサル頂点を3色目で塗り分けられる。n が偶数の場合、 W_n は彩色数が4であり、n ≥ 6 でパーフェクトグラフではなくなる。 W₇ はユークリッド平面上で唯一単位距離グラフである。

  車輪グラフ W_n の彩色多項式は、 $P_{W_{n}}(x)=x((x-2)^{(n-1)}-(-1)^{n}(x-2))$ カテゴリ / コモンズ