車輪グラフのソースを表示

{{混同|円グラフ}}
{{infobox graph
 | name = 車輪グラフ
 | image = [[Image:Wheel graphs.svg|220px]]
 | image_caption = 車輪グラフの例
 | girth   = 3
 | diameter = 1 (''n'' = 4)<br>2 (''n'' > 4)
 | vertices = ''n''
 | edges = 2(''n'' - 1)
 | chromatic_number = 3 （''n'' が奇数の場合）<br/>4 （''n'' が偶数の場合）
 | chromatic_index =
 | spectrum = <math>\{2 \cos(2 k \pi / (n-1))^1; </math><br><math>k = 1, \ldots, n - 2\}</math><math>\cup \{1 \pm \sqrt{n}\}</math>
 | properties = [[ハミルトングラフ]]<br>[[双対|自己双対]]<br>[[平面グラフ]]
 | notation = ''W''<sub>''n''</sub>
}}

'''車輪グラフ'''（しゃりんグラフ、[[英語|英]]: Wheel graph）とは、[[グラフ理論]]のグラフの1つであり、[[閉路グラフ]]と、そのすべての頂点に接続するユニバーサル頂点（支配頂点）と呼ばれる頂点からなるグラフである。''n'' 頂点の車輪グラフは、 ''n'' - 1[[角錐]]の、1-{{仮リンク|n 骨格|en|n-skeleton|label=骨格}}とも定義できる（3 < ''n'')。''n'' 頂点の車輪グラフを''W''<sub>''n''</sub>で表したり<ref>{{mathworld | urlname = WheelGraph | title = Wheel Graph}}</ref>、''n'' + 1 頂点の車輪グラフを、 ''n'' 角形で表せることから ''W''<sub>''n''</sub>で表したりする<ref>{{cite book |last=Rosen |first=Kenneth H. |year=2011 |title=Discrete Mathematics and Its Applications |edition=7th |publisher=McGraw-Hill |page=655 |isbn=0073383090}}</ref>。本記事内では、前者の表記を用いる。

== 内包表記での構成 ==
頂点集合 {1, 2, 3, …, ''v'' }に対し辺の集合は[[集合|内包表記]]で{{1, 2}, {1, 3}, …, {1, ''v''}, {2, 3}, {3, 4}, …, {''v'' - 1, ''v''}, {''v'' ,2}}と表せる<ref>{{cite book|last=Trudeau|first=Richard J.|title=Introduction to Graph Theory|year=1993|publisher=Dover Pub.|location=New York|isbn=978-0-486-67870-2|pages=56|url=http://store.doverpublications.com/0486678709.html|edition=Corrected, enlarged republication.|accessdate=8 August 2012}}</ref>。
ここで、頂点1がユニバーサル頂点であり、頂点2から頂点 ''v'' は閉路グラフを構成する。

== 性質 ==
車輪グラフは
* [[平面グラフ]]であり、一意な平面グラフを持つ。
** 車輪グラフは[[ハリングラフ]]（[[木_(数学)|木]]（グラフ）の葉を閉路でつないだ平面グラフ）である。
* 車輪グラフは自己双対である。
* 最大平面グラフは、''K''<sub>4</sub> = ''W''<sub>4</sub>であるか、''W''<sub>5</sub> か ''W''<sub>6</sub>を部分グラフとして含む。
* ''n'' - 1 種類の[[ハミルトン閉路]]をもつ
* ''W''<sub>n</sub>に対して<math>n^2-3n+3</math>種類の閉路が存在する{{OEIS|id=A002061}}。
**ユニバーサル頂点以外の閉路が1、ユニバーサル頂点を含む''m'' （3 <= ''m'' <= n）頂点の閉路が''n'' - 1個の、合計(''n'' - 1)(''n'' - 2) + 1個である。

{| class="wikitable skin-invert-image"
|[[Image:CyclesW4.svg|320px]]<BR>車輪グラフ''W''<sub>4</sub>に含まれる7種類の閉路。<br>下3つはすべての頂点を通るため、ハミルトン閉路である。
|}

''n'' が奇数の場合、 ''W''<sub>''n''</sub> は[[グラフ彩色|彩色数]]3の[[パーフェクトグラフ]]である。つまり、ユニバーサル頂点以外の頂点を交互に2色に塗り分け、中央のユニバーサル頂点を3色目で塗り分けられる。''n'' が偶数の場合、 ''W''<sub>''n''</sub> は彩色数が4であり、''n'' ≥ 6 でパーフェクトグラフではなくなる。 ''W''<sub>7</sub> は[[ユークリッド平面]]上で唯一[[単位距離グラフ]]である<ref>{{citation
  | last1 = Buckley | first1 = Fred | last2 = Harary | first2 = Frank | author2-link = Frank Harary
  | title = On the euclidean dimension of a wheel
  | journal = [[Graphs and Combinatorics]]
  | volume = 4
  | issue = 1
  | year = 1988
  | doi = 10.1007/BF01864150
  | pages = 23–30}}.</ref> 

車輪グラフ ''W<sub>n</sub>'' の[[グラフ彩色#彩色多項式|彩色多項式]]は、<math>P_{W_n}(x)=x((x-2)^{(n-1)}-(-1)^{n}(x-2))</math>である。

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

車輪グラフ ''W''<sub>6</sub> は、[[ラムゼー理論]]における[[ポール・エルデシュ]]の予想（下記）の反例となった。
ポール・エルデシュは、「彩色数が同じグラフでは、[[完全グラフ]]が[[ラムゼー理論|ラムゼー数]]が最小となるグラフである」と予想した。しかし、Faudree と McKay は1993年に ''W''<sub>6</sub> はラムゼー数が17であり、同じ彩色数を持つ完全グラフ ''K''<sub>4</sub>　のラムゼー数である18より小さいことを示し、反例とした<ref>{{citation
  | last1 = Faudree | first1 = Ralph J. | author1-link = Ralph Faudree
  | last2 = McKay | first2 = Brendan D. | author2-link = Brendan McKay
  | title = A conjecture of Erdős and the Ramsey number ''r''(''W''<sub>6</sub>)
  | url = http://cs.anu.edu.au/people/Brendan.McKay/papers/wheels.ps.gz
  | journal = J. Combinatorial Math. and Combinatorial Comput. <!-- comment to prevent DOI bot from breaking the journal name again -->
  | volume = 13
  | year = 1993
  | pages = 23–31}}.</ref>。つまり、すべての17頂点のグラフ ''G''について、 ''G''またはその補グラフのどちらかが部分グラフとして ''W''<sub>6</sub> を含む一方で、17頂点の{{仮リンク|パリーグラフ|en| Paley graph}}もその補グラフも完全グラフ ''K''<sub>4</sub>を含まない。

== 注釈・出典 ==
{{reflist}}

{{Graph Theory-footer}}

{{DEFAULTSORT:しやりんくらふ}}
[[Category:グラフ理論のグラフ]]
[[Category:数学に関する記事]]