Wheel graph

Wheel graph
Wheel graph
	Several examples of wheel graphs
Vertices	n ≥ 4
Edges	2(n − 1)
Diameter	2 if n > 4; 1 if n = 4
Girth	3
Chromatic number	4 if n is even; 3 if n is odd
Spectrum	;
Properties	Hamiltonian; Self-dual; Planar
Notation	Wn
	Table of graphs and parameters

In the mathematical discipline of graph theory, a wheel graph is a graph formed by connecting a single universal vertex to all vertices of a cycle. A wheel graph with $n$ vertices can also be defined as the 1-skeleton of an ( $n - 1$ )-gonal pyramid.

Some authors^[1] write $W n$ to denote a wheel graph with $n$ vertices ( $n \geq 4$ ); other authors^[2] instead use $W n$ to denote a wheel graph with $n + 1$ vertices ( $n \geq 3$ ), which is formed by connecting a single vertex to all vertices of a cycle of length $n$ . The former notation is used in the rest of this article and in the table on the right.

Edge Set

{{1, 2}, {1, 3}, …, {1, v}, {2, 3}, {3, 4}, …, {v − 1, v}, {v, 2}}^[3] would be the edge set of a wheel graph with vertex set {1, 2, …, v} in which the vertex 1 is a universal vertex.

Properties

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

There is always a Hamiltonian cycle in the wheel graph and there are $n^{2}-3n+3$ cycles in W_n (sequence A002061 in the OEIS).

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.^[4]

The chromatic polynomial of the wheel graph W_n is :

P_{W_{n}}(x)=x((x-2)^{(n-1)}-(-1)^{n}(x-2)).

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 graphic 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.^[5] 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

^ Weisstein, Eric W. "Wheel Graph". MathWorld.
^ Rosen, Kenneth H. (2011). Discrete Mathematics and Its Applications (7th ed.). McGraw-Hill. p. 655. ISBN 978-0073383095.
^ Trudeau, Richard J. (1993). Introduction to Graph Theory (Corrected, enlarged republication. ed.). New York: Dover Pub. p. 56. ISBN 978-0-486-67870-2. Retrieved 8 August 2012.
^ Buckley, Fred; Harary, Frank (1988), "On the euclidean dimension of a wheel", Graphs and Combinatorics, 4 (1): 23–30, doi:10.1007/BF01864150, S2CID 44596093.
^ Faudree, Ralph J.; McKay, Brendan D. (1993), "A conjecture of Erdős and the Ramsey number r(W₆)", J. Combinatorial Math. and Combinatorial Comput., 13: 23–31.

[1] Weisstein, Eric W. "Wheel Graph". MathWorld.

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

[3] Trudeau, Richard J. (1993). Introduction to Graph Theory (Corrected, enlarged republication. ed.). New York: Dover Pub. p. 56. ISBN 978-0-486-67870-2. Retrieved 8 August 2012.

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

[5] Faudree, Ralph J.; McKay, Brendan D. (1993), "A conjecture of Erdős and the Ramsey number r(W₆)", J. Combinatorial Math. and Combinatorial Comput., 13: 23–31.

[1]

[2]

[3]

[4]

[5]