跳至內容

用戶:Tenpages/輪圖

維基百科,自由的百科全書
輪圖
輪圖的一些例子
頂點n
2(n − 1)
直徑2,如果n > 4
1,如果n = 4
圍長3
色數4,如果n是偶數
3,如果n是奇數
屬性哈密頓圖
自對偶
平面圖

圖論這一數學分支中,輪圖wheel graph)是指一個完全點連接到一個循環圖上所有節點而形成的圖。一些文獻中[1]會使用記號Wn來表示有n個節點(n ≥ 4)的輪圖;另一些文獻中[2]則使用Wn來表示有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。輪圖是自對偶的:輪圖的平面對偶和其自身同構。除了K4 = W4之外,每個極大平面圖都有一個形如W5W6的子圖。

任意輪圖中總有哈密頓環Wn中有OEIS數列A002061)。

輪圖W4中的7個環

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

輪圖Wn色多項式

擬陣論中,兩類重要的擬陣輪擬陣(英語:wheel matroids)和旋擬陣(英語:whirl matroids)的概念都是輪圖的推廣。

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

參考資料

[編輯]
  1. ^ 埃里克·韋斯坦因. Wheel Graph. MathWorld. 
  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. 
  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(W6), J. Combinatorial Math. and Combinatorial Comput., 1993, 13: 23–31 .