Wheel graph

infobox graph
name = Wheel graph


image_caption = Several examples of wheel graphs
vertices = "n"
edges = 2("n" − 1)
chromatic_number = 3 if "n" is odd 4 if "n" is even
chromatic_index =

In the mathematical discipline of graph theory, a wheel graph "W"_"n" is a graph with "n" vertices, formed by connecting a single vertex to all vertices of an ("n"-1)-cycle. The numerical notation for wheels is used inconsistently in the literature: some authors instead use "n" to refer to the length of the cycle, so that their "W"_"n" is the graph we denote "W"_"n+1". A wheel graph can also be defined as the 1-skeleton of an ("n"-1)-gonal pyramid.

Wheel graphs are planar graphs, and as such have a unique planar embedding. They are self-dual: the planar dual of any wheel graph is an isomorphic graph. Any maximal planar graph, other than "K"₄ = "W"₄, contains as a subgraph either "W"₅ or "W"₆.

For odd values of "n", "W"_"n" is a perfect graph with chromatic number 3: the vertices of the cycle can be given two colors, and the center vertex given a third color. For even "n", "W"_"n" has chromatic number 4, and (when "n" ≥ 6) is not perfect. "W"₇ is the only wheel graph that is a unit distance graph in the Euclidean plane (Buckley and Harary 1988).

In matroid theory, two particularly important special classes of matroids are the "wheel matroids" and the "whirl matroids", both derived from wheel graphs. The "k"-wheel matroid is the cycle matroid of a wheel "W"_"k+1", while the "k"-whirl matroid is derived from the "k"-wheel by considering the outer cycle of the wheel, as well as all of its spanning trees, to be independent.

The wheel "W"₆ supplied a counterexample to a conjecture of Paul Erdős on Ramsey theory: he had conjectured that the complete graph has the smallest Ramsey number among all graphs with the same chromatic number, but Faudree and McKay (1993) showed "W"₆ has Ramsey number 17 while the complete graph with the same chromatic number, "K"₄, has Ramsey number 18. That is, for every 17-vertex graph "G", either "G" or its complement contains "W"₆ as a subgraph, while neither the 17-vertex Paley graph nor its complement contains a copy of "K"₄.

References

*cite journal
author = Buckley, Fred; Harary, Frank
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

*cite journal
author = Faudree, Ralph J.; McKay, Brendan D.
title = A conjecture of Erdős and the Ramsey number "r"("W"₆)
url = http://cs.anu.edu.au/people/Brendan.McKay/papers/wheels.ps.gz
journal = J. Combinatorial Math. and Combinatorial Comput.
volume = 13
year = 1993
pages = 23–31

External links

*mathworld | urlname = WheelGraph | title = Wheel Graph