車輪グラフ

車輪グラフ (Wn) について

車輪グラフとは、グラフ理論において特有の構造を持つグラフの一種で、一般に「Wn」で表示されます。このグラフは、n頂点を持つ閉路と、その全ての頂点に接続されるひとつのユニバーサル頂点（支配頂点）から構成されています。具体的には、3より大きいnに対して定義され、n-1の角が形成されます。このユニバーサル頂点は、他の全ての頂点と直接接続されています。

車輪グラフの構成

車輪グラフの辺の集合は、内包表記を使用して次のように表現されます。
{ {1, 2}, {1, 3}, …, {1, v}, {2, 3}, {3, 4}, …, {v - 1, v}, {v ,2} }
ここで、頂点1はユニバーサル頂点として機能し、残りの頂点は閉路を構成します。

車輪グラフの性質

車輪グラフにはいくつか注目すべき性質があります。まず、車輪グラフは平面グラフであり、一意の平面グラフを持つことが保証されています。また、ハリングラフとしての性質も兼ね備え、自己双対性を示すことが知られています。

最大平面グラフはK4またはW4であり、W5やW6を部分グラフとして含むことができます。また、n-1個のハミルトン閉路を持つため、様々な閉路構成が可能です。具体的には、ユニバーサル頂点以外の閉路が1つあり、ユニバーサル頂点を含むm (3 ≤ m ≤ n) 頂点の閉路がn-1個存在し、トータルでは合計(n-1)(n-2)+1個の閉路があります。

彩色数と特性

nが奇数の際には、Wnは彩色数3を持つパーフェクトグラフとして機能します。つまり、ユニバーサル頂点を含む他の頂点は2色で交互に塗り分けられ、中央のユニバーサル頂点は別の色で塗れるため、視覚的にも分かりやすい構造を持っています。一方、nが偶数の場合は、彩色数が4となり、nが6以上になるとパーフェクトグラフではなくなります。

また、特にW7はユークリッド平面上における唯一の単位距離グラフです。

彩色多項式

Wnの彩色多項式は、次の式で定義されます。
P(Wn)(x) = x((x - 2)^(n - 1) - (-1)^n (x - 2))
この表現を通じて、グラフの特性に基づく多様な解析が可能になります。

マトロイド理論との関連

マトロイドに関する分野では、特に重要なクラスとしてwheel matroidsとwhirl matroidsがあります。これらは車輪グラフから導き出された構造であり、k-wheelマトロイドはWk+1の閉路マトロイドを指し、k-whirlマトロイドはwheelマトロイドの周囲の閉路と全ての全域木が独立していると見做されます。

ポール・エルデシュの予想

学術界において特に興味深いのは、車輪グラフW6がラムゼー理論に関するポール・エルデシュの予想に対する反例となったことです。エルデシュは同彩色数を持つグラフの中で、完全グラフが最小ラムゼー数を持つと予想しましたが、1993年にFaudreeとMcKayは、W6のラムゼー数が17であることを示しました。これは、同じ彩色数を持つ完全グラフK4のラムゼー数18より小さく、予想を覆す重要な発見となりました。このように、車輪グラフはグラフ理論とその関連分野における多くの重要な洞察を提供します。

もう一度検索