Articles

車輪グラフ

離散数学 > グラフ理論 > 単純グラフ > 円錐グラフ >
離散数学 > グラフ理論 > 単純グラフ > 優美なグラフ >
離散数学 > グラフ理論 > 単純グラフ > 積分グラフ >

DOWNLOAD Mathematica NotebookWheelGraphs

この著作で定義されている通りです。 は、次数nのホイールグラフW_nであり、単にnホイールと呼ばれることもある(Harary 1994, p. 46; Pemmaraju and Skiena 2003, p.248; Tutte 2005, p.78)、次数n-1のサイクルを含み、サイクルの全てのグラフ頂点がハブと呼ばれる他のグラフ頂点に接続されているグラフである。 ハブを含む輪の辺をスポークと呼ぶ(Skiena 1990, p. 146)。 車輪W_nはグラフ結合K_1+C_(n-1)として定義でき、K_1はシングルトングラフ、C_nはサイクルグラフで、(n,1)-コーングラフとなる。

なお、車輪グラフのインデックス付けには2通りの慣例があり、著者によっては(例えば,

四面体グラフ(つまりK_4)はW_4に、W_5は完全三面体グラフK_(1,2,2)に同型であることに注意してほしい。 一般にn輪グラフは(n-1)ピラミッドの骨格である。

W_5はペンタトープグラフK_5から2辺を削除して得られるグラフの一つで、もう一つは家Xグラフ。

輪グラフは潔い(Frucht 1979)。

車輪グラフW_nn=7ではグラフ次元2(つまり単位距離)、それ以外では次元3(つまり単位距離ではない)(Erdős et al. 1965, Buckley and Harary 1988).

任意の車輪グラフは自己双対グラフとなる.

Wolfram Languageで車輪グラフの作成はWheelGraphでできる.Wheel GraphはWhiteGraphで作成できる。

WheelGraphCycles4WheelGraphCycles5

ホイールグラフW_nのグラフサイクルの数はn^2-3n+3で与えられ、7, 13, 21, 31, 43, 57, …である。 (OEIS A002061) for n=4, 5, …

車輪グラフにおいて、ハブは次数n-1、他のノードは次数3。 車輪グラフは3-連結である。 W_4=K_4ここで、K_4は次数4の完全グラフ。 W_nの色数は

 chi(W_n)={3 for n odd; 4 for n even.
(1)

であり、このグラフを見ると ホイールグラフ W_n は色度多項式

 pi(x)=x.
(2)

となる。