ホイールグラフ

ホイールグラフ
ホイールグラフのいくつかの例
頂点	4以上
エッジ	2( n − 1) の
直径	n > 4の場合は 2、n = 4 の場合は 1
胴回り	3
彩度数	nが偶数の場合は4、nが奇数の 場合は3
スペクトラム	${\displaystyle \{2\cos(2k\pi /(n-1))^{1};}$ ${\displaystyle k=1,\ldots ,n-2\}}$${\displaystyle \cup \{1\pm {\sqrt {n}}\}}$
プロパティ	ハミルトン 自己双対 平面
表記	W n
グラフとパラメータの表

グラフ理論において、ホイールグラフは、単一のユニバーサル頂点をサイクルのすべての頂点に接続することによって形成されるグラフです。 n頂点を持つホイールグラフは、( n -1 )角錐の1スケルトンとして定義することもできます。

一部の著者^[1]は、 n 個の頂点( n ≥ 4 )を持つホイールグラフを表すためにW _nと書きます。他の著者^[2]は、代わりに、長さ_{nのサイクルのすべての頂点に単一の頂点を接続することによって形成される}n + 1 個の頂点 ( n ≥ 3 ) を持つホイールグラフを表すためにW nを使用します。前者の表記法は、この記事の残りの部分と右側の表で使用されます。

{{1, 2}, {1, 3}, …, {1, v}, {2, 3}, {3, 4}, …, {v − 1, v}, {v, 2}} ^{[3]は、頂点1が}普遍頂点である頂点集合{1, 2, …, v}を持つホイールグラフの辺集合となる。

ホイール グラフは平面グラフであり、一意の平面埋め込みを持ちます。より具体的には、すべてのホイール グラフはHalin グラフです。これらは自己双対です。つまり、すべてのホイール グラフの平面双対は同型グラフです。K 4 = W ₄以外のすべての最大平面グラフには、サブグラフとしてW ₅またはW _{6 のいずれ}かが含まれます。

ホイールグラフには常にハミルトンサイクルがあり、 W _n ( OEISのシーケンスA002061 )にもサイクルがあります。 ${\displaystyle n^{2}-3n+3}$

nが奇数の場合、W _{n は}彩度数3の完全グラフである。つまり、サイクルの頂点には 2 色、中心の頂点には 3 色目を割り当てることができる。nが偶数の場合、W _{n は}彩度数4となり、( n ≥ 6 のとき) 完全ではない。 W ₇はユークリッド平面で単位距離グラフとなる唯一のホイールグラフである。 ^[4]

ホイールグラフW _nの彩色多項式は次のようになる。

${\displaystyle P_{W_{n}}(x)=x((x-2)^{(n-1)}-(-1)^{n}(x-2)).}$

マトロイド理論では、マトロイドの特に重要な 2 つの特殊クラスは、ホイール マトロイドと渦巻きマトロイドであり、どちらもホイール グラフから派生しています。kホイール マトロイドは、ホイールW _k+1のグラフィック マトロイドであり、k渦巻きマトロイドは、ホイールの外側のサイクルとそのすべてのスパニング ツリーが独立していると見なすことによって、 kホイールから派生します。

ホイールW _{6 は、}ラムゼー理論に関するポール・エルデシュの予想に対する反例となった。エルデシュは、同じ彩色数を持つすべてのグラフの中で、完全グラフのラムゼー数が最小になると予想していたが、Faudree と McKay (1993) は、W _{6 の}ラムゼー数は17であるのに対し、同じ彩色数を持つ完全グラフK ₄のラムゼー数は18であることを示した^。[5]つまり、17頂点のグラフGごとに、Gまたはその補グラフにW _{6 が}サブグラフとして含まれるが、17頂点のペイリーグラフにもその補グラフにもK ₄のコピーは含まれない。