輪圖

輪圖
	輪圖的一些例子
頂點	n
邊	2(n − 1)
直徑	2，如果n > 4; 1，如果n = 4
圍長	3
色數	4，如果n是偶數; 3，如果n是奇數
屬性	哈密頓圖; 自對偶; 平面圖
	閱; 論; 編;

在圖論這一數學分支中，輪圖（wheel graph）是指一個完全點連接到一個循環圖上所有節點而形成的圖。一些文獻中^[1]會使用記號W_n來表示有n個節點（n ≥ 4）的輪圖；另一些文獻中^[2]則使用W_n來表示有n+1個節點（n ≥ 3）的輪圖，這裏n是指形成輪圖的循環圖中節點的數量。在本條目中使用前一種記號。

構造[編輯]

給定一個點集{1, 2, 3, …, v}，則若使用集合建構式符號，輪圖的邊集可以表示為{{1, 2}, {1, 3}, …, {1, v}, {2, 3}, {3, 4}, …, {v − 1, v}, {v, 2}}。^[3]

性質[編輯]

輪圖是平面圖，因此有唯一的平面嵌入。更進一步，每個輪圖都是哈林圖（英語：Halin graph）。輪圖是自對偶的：輪圖的平面對偶和其自身同構。除了K₄ = W₄之外，每個極大平面圖都有一個形如W₅或W₆的子圖。

任意輪圖中總有哈密頓環。W_n中有 $n^{2}-3n+3$ 個環（OEIS數列A002061）。

當n為奇數時，W_n是一個完美圖（英語：perfect graph），其色數為3：環上的節點可以用兩種顏色染色，而中間的完全點使用第三種顏色。當n為偶數時，W_n的色數為4，且當n ≥ 6時不是完美圖。W₇是輪圖中在歐幾里得平面上的唯一一個單位距離圖（英語：unit distance graph）^[4]。

輪圖W_n的色多項式為 $P_{W_{n}}(x)=x((x-2)^{(n-1)}-(-1)^{n}(x-2))$ 。

在擬陣論中，兩類重要的擬陣輪擬陣（英語：wheel matroids）和旋擬陣（英語：whirl matroids）的概念都是輪圖的推廣。

輪圖W₆是埃爾德什·帕爾對拉姆齊理論一個猜想的反例：他猜想在色數相同的圖中，完全圖的拉姆齊數是最小的。但後來有研究發現W₆的拉姆齊數是17，而與之色數相同的完全圖K₄的拉姆齊數則是18^[5]。也就是說，對於任意17節點的圖G，G或它的補圖一定有子圖W₆；而17節點的Paley圖（英語：Paley graph）和它的補圖都沒有子圖K₄。

參考資料[編輯]

^ Weisstein, Eric W. (編). Wheel Graph. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. （英語）.
^ Rosen, Kenneth H. Discrete Mathematics and Its Applications 7th. McGraw-Hill. 2011: 655. ISBN 978-0073383095.
^ Trudeau, Richard J. Introduction to Graph Theory Corrected, enlarged republication. New York: Dover Pub. 1993: 56 [8 August 2012]. ISBN 978-0-486-67870-2. （原始內容存檔於2019-05-05）.
^ Buckley, Fred; Harary, Frank, On the euclidean dimension of a wheel, Graphs and Combinatorics, 1988, 4 (1): 23–30, doi:10.1007/BF01864150 .
^ Faudree, Ralph J.; McKay, Brendan D., A conjecture of Erdős and the Ramsey number r(W₆), J. Combinatorial Math. and Combinatorial Comput., 1993, 13: 23–31 [2021-08-21], （原始內容存檔於2012-02-05） .

[1] Weisstein, Eric W. (編). Wheel Graph. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. （英語）.

[2] Rosen, Kenneth H. Discrete Mathematics and Its Applications 7th. McGraw-Hill. 2011: 655. ISBN 978-0073383095.

[3] Trudeau, Richard J. Introduction to Graph Theory Corrected, enlarged republication. New York: Dover Pub. 1993: 56 [8 August 2012]. ISBN 978-0-486-67870-2. （原始內容存檔於2019-05-05）.

[4] Buckley, Fred; Harary, Frank, On the euclidean dimension of a wheel, Graphs and Combinatorics, 1988, 4 (1): 23–30, doi:10.1007/BF01864150 .

[5] Faudree, Ralph J.; McKay, Brendan D., A conjecture of Erdős and the Ramsey number r(W₆), J. Combinatorial Math. and Combinatorial Comput., 1993, 13: 23–31 [2021-08-21], （原始內容存檔於2012-02-05） .

[1]

[2]

[3]

[4]

[5]