PROFILPELAJAR.COM

車輪グラフ
	車輪グラフの例
頂点	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で表したり^[1]、n + 1 頂点の車輪グラフを、 n 角形で表せることから W_nで表したりする^[2]。本記事内では、前者の表記を用いる。

内包表記での構成

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

性質

車輪グラフは

平面グラフであり、一意な平面グラフを持つ。
- 車輪グラフはハリングラフ（木（グラフ）の葉を閉路でつないだ平面グラフ）である。
車輪グラフは自己双対である。
最大平面グラフは、K₄ = W₄であるか、W₅ か W₆を部分グラフとして含む。
n - 1 種類のハミルトン閉路をもつ
W_nに対して $n^{2}-3n+3$ $n^{2}-3n+3$ 種類の閉路が存在するオンライン整数列大辞典の数列 A002061。
- ユニバーサル頂点以外の閉路が1、ユニバーサル頂点を含むm （3 <= m <= n）頂点の閉路がn - 1個の、合計(n - 1)(n - 2) + 1個である。

車輪グラフW₄に含まれる7種類の閉路。下3つはすべての頂点を通るため、ハミルトン閉路である。

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

車輪グラフ W_n の彩色多項式は、 $P_{W_{n}}(x)=x((x-2)^{(n-1)}-(-1)^{n}(x-2))$ である。

マトロイドの分野では、特に重要な特殊なクラスに wheel matroids と whirl matroids　があり、これらは車輪グラフから導かれる。 k-wheel マトロイドは、W_k+1の閉路マトロイドであり、 k-whirl マトロイドは、 wheelマトロイドの外側の閉路とそのすべての全域木が独立しているとみなすことによって、 k wheelマトロイドから導かれる。

車輪グラフ W₆ は、ラムゼー理論におけるポール・エルデシュの予想（下記）の反例となった。ポール・エルデシュは、「彩色数が同じグラフでは、完全グラフがラムゼー数が最小となるグラフである」と予想した。しかし、Faudree と McKay は1993年に W₆ はラムゼー数が17であり、同じ彩色数を持つ完全グラフ K₄　のラムゼー数である18より小さいことを示し、反例とした^[5]。つまり、すべての17頂点のグラフ Gについて、 Gまたはその補グラフのどちらかが部分グラフとして W₆ を含む一方で、17頂点のパリーグラフ（英語版）もその補グラフも完全グラフ K₄を含まない。