車輪グラフ – Wikipedia

Posted on by

車輪グラフ（しゃりんグラフ、英: Wheel graph）とは、グラフ理論のグラフの1つであり、閉路グラフと、そのすべての頂点に接続するユニバーサル頂点（支配頂点）と呼ばれる頂点からなるグラフである。n 頂点の車輪グラフは、 n – 1角錐の、1-骨格（英語版）とも定義できる（3 < n)。n 頂点の車輪グラフをWnで表したり[1]、n + 1 頂点の車輪グラフを、 n 角形で表せることから Wnで表したりする[2]。本記事内では、前者の表記を用いる。

内包表記での構成[編集]

頂点集合 {1, 2, 3, …, v }に対し辺の集合は内包表記で{{1, 2}, {1, 3}, …, {1, v}, {2, 3}, {3, 4}, …, {v – 1, v}, {v ,2}}と表せる[3]。
ここで、頂点1がユニバーサル頂点であり、頂点2から頂点 v は閉路グラフを構成する。

車輪グラフは

  • 平面グラフであり、一意な平面グラフを持つ。
    • 車輪グラフはハリングラフ（木（グラフ）の葉を閉路でつないだ平面グラフ）である。
  • 車輪グラフは自己双対である。
  • 最大平面グラフは、K4 = W4であるか、W5 か W6を部分グラフとして含む。
  • n – 1 種類のハミルトン閉路をもつ
  • Wnに対して
    n2−3n+3{displaystyle n^{2}-3n+3}

    種類の閉路が存在するオンライン整数列大辞典の数列 A002061。
    • ユニバーサル頂点以外の閉路が1、ユニバーサル頂点を含むm （3 <= m <= n）頂点の閉路がn – 1個の、合計(n – 1)(n – 2) + 1個である。

車輪グラフW4に含まれる7種類の閉路。
下3つはすべての頂点を通るため、ハミルトン閉路である。

n が奇数の場合、 Wn は彩色数3のパーフェクトグラフである。つまり、ユニバーサル頂点以外の頂点を交互に2色に塗り分け、中央のユニバーサル頂点を3色目で塗り分けられる。n が偶数の場合、 Wn は彩色数が4であり、n ≥ 6 でパーフェクトグラフではなくなる。 W7 はユークリッド平面上で唯一単位距離グラフである[4]

車輪グラフ Wn の彩色多項式は、

PWn(x)=x((x−2)(n−1)−(−1)n(x−2)){displaystyle P_{W_{n}}(x)=x((x-2)^{(n-1)}-(-1)^{n}(x-2))}

である。

マトロイドの分野では、特に重要な特殊なクラスに wheel matroids と whirl matroids　があり、これらは車輪グラフから導かれる。 k-wheel マトロイドは、Wk+1の閉路マトロイドであり、 k-whirl マトロイドは、 wheelマトロイドの外側の閉路とそのすべての全域木が独立しているとみなすことによって、 k wheelマトロイドから導かれる。

車輪グラフ W6 は、ラムゼー理論におけるポール・エルデシュの予想（下記）の反例となった。
ポール・エルデシュは、「彩色数が同じグラフでは、完全グラフがラムゼー数が最小となるグラフである」と予想した。しかし、Faudree と McKay は1993年に W6 はラムゼー数が17であり、同じ彩色数を持つ完全グラフ K4　のラムゼー数である18より小さいことを示し、反例とした[5]。つまり、すべての17頂点のグラフ Gについて、 Gまたはその補グラフのどちらかが部分グラフとして W6 を含む一方で、17頂点のパリーグラフ（英語版）もその補グラフも完全グラフ K4を含まない。

注釈・出典[編集]

  1. ^ Weisstein, Eric W. “Wheel Graph“. MathWorld (英語).
  2. ^ Rosen, Kenneth H. (2011). Discrete Mathematics and Its Applications (7th ed.). McGraw-Hill. p. 655. ISBN 0073383090 
  3. ^ Trudeau, Richard J. (1993). Introduction to Graph Theory (Corrected, enlarged republication. ed.). New York: Dover Pub.. pp. 56. ISBN 978-0-486-67870-2. http://store.doverpublications.com/0486678709.html 2012年8月8日閲覧。 
  4. ^ Buckley, Fred; Harary, Frank (1988), “On the euclidean dimension of a wheel”, Graphs and Combinatorics 4 (1): 23–30, doi:10.1007/BF01864150 .
  5. ^ Faudree, Ralph J.; McKay, Brendan D. (1993), “A conjecture of Erdős and the Ramsey number r(W6)”, J. Combinatorial Math. and Combinatorial Comput. 13: 23–31, http://cs.anu.edu.au/people/Brendan.McKay/papers/wheels.ps.gz .