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 | [math]\displaystyle{ \{2\cos(2k\pi / (n - 1))^1; }[/math] [math]\displaystyle{ k = 1, \ldots, n - 2\} }[/math][math]\displaystyle{ \cup\{1 \pm \sqrt{n}\} }[/math] |
| 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 Wn to denote a wheel graph with n vertices (n ≥ 4); other authors[2] instead use Wn to denote a wheel graph with n + 1 vertices (n ≥ 3), which is formed by connecting a single vertex to all vertices of a cycle of length n. The rest of this article uses the former notation.
Set-builder construction
Given a vertex set of {1, 2, 3, …, v}, the edge set of the wheel graph can be represented in set-builder notation by {{1, 2}, {1, 3}, …, {1, v}, {2, 3}, {3, 4}, …, {v − 1, v}, {v, 2}}.[3]
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 K4 = W4, contains as a subgraph either W5 or W6.
There is always a Hamiltonian cycle in the wheel graph and there are [math]\displaystyle{ n^2-3n+3 }[/math] cycles in Wn (sequence A002061 in the OEIS).
For odd values of n, Wn 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, Wn has chromatic number 4, and (when n ≥ 6) is not perfect. W7 is the only wheel graph that is a unit distance graph in the Euclidean plane.[4]
The chromatic polynomial of the wheel graph Wn is :
- [math]\displaystyle{ P_{W_n}(x) = x((x - 2)^{(n - 1)} - (-1)^n(x - 2)). }[/math]
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 Wk+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 W6 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 W6 has Ramsey number 17 while the complete graph with the same chromatic number, K4, has Ramsey number 18.[5] That is, for every 17-vertex graph G, either G or its complement contains W6 as a subgraph, while neither the 17-vertex Paley graph nor its complement contains a copy of K4.
References
- ↑ Weisstein, Eric W.. "Wheel Graph". http://mathworld.wolfram.com/WheelGraph.html.
- ↑ Rosen, Kenneth H. (2011). Discrete Mathematics and Its Applications (7th ed.). McGraw-Hill. p. 655. ISBN 978-0073383095. https://archive.org/details/discretemathemat00rose_408.
- ↑ 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. Retrieved 8 August 2012.
- ↑ "On the euclidean dimension of a wheel", Graphs and Combinatorics 4 (1): 23–30, 1988, doi:10.1007/BF01864150.
- ↑ "A conjecture of Erdős and the Ramsey number r(W6)", J. Combinatorial Math. and Combinatorial Comput. 13: 23–31, 1993, http://cs.anu.edu.au/people/Brendan.McKay/papers/wheels.ps.gz.
 |  |
