graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, a wheel graph is a graph formed by connecting a single

universal vertex In graph theory, a universal vertex is a Vertex (graph theory), vertex of an undirected graph that is adjacent to all other vertices of the graph. It may also be called a dominating vertex, as it forms a one-element dominating set in the graph. A ...

to all vertices of a cycle. A wheel graph with vertices can also be defined as the 1-

skeleton A skeleton is the structural frame that supports the body of most animals. There are several types of skeletons, including the exoskeleton, which is a rigid outer shell that holds up an organism's shape; the endoskeleton, a rigid internal fra ...

of an

pyramid A pyramid () is a structure whose visible surfaces are triangular in broad outline and converge toward the top, making the appearance roughly a pyramid in the geometric sense. The base of a pyramid can be of any polygon shape, such as trian ...

. Some authors write to denote a wheel graph with vertices (); other authors instead use to denote a wheel graph with vertices (), which is formed by connecting a single vertex to all vertices of a cycle of length . The former notation is used in the rest of this article and in the table on the right.

Edge Set

would be the edge set of a wheel graph with vertex set in which the vertex 1 is a

Properties

Wheel graphs are

planar graph In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...

s, and have a unique planar embedding. More specifically, every wheel graph is a

Halin graph In graph theory, a Halin graph is a type of planar graph, constructed by connecting the leaves of a tree (graph theory), tree into a cycle. The tree must have at least four vertices, none of which has exactly two neighbors; it should be drawn in ...

. 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 mathematics, mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path (graph theory), path in an undirected or directed graph that visits each vertex (graph theory), vertex exactly once. A Hamiltonian cycle (or ...

in the wheel graph and there are

n^2-3n+3

cycles in ''W''_''n'' . For odd values of ''n'', ''W''_''n'' is a

perfect graph In graph theory, a perfect graph is a Graph (discrete mathematics), graph in which the Graph coloring, chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic nu ...

with

chromatic number In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring i ...

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

4, and (when ''n'' ≥ 6) is not perfect. ''W''₇ is the only wheel graph that is a

unit distance graph In mathematics, particularly geometric graph theory, a unit distance graph is a Graph (discrete mathematics), graph formed from a collection of points in the Euclidean plane by connecting two points whenever the distance between them is exactly o ...

in the Euclidean plane. The

chromatic polynomial The chromatic polynomial is a graph polynomial studied in algebraic graph theory, a branch of mathematics. It counts the number of graph colorings as a function of the number of colors and was originally defined by George David Birkhoff to stud ...

of the wheel graph ''W_n'' is : :

P_(x) = x((x - 2)^ - (-1)^n(x - 2)).

matroid In combinatorics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid Axiomatic system, axiomatically, the most significant being in terms ...

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 In the mathematical theory of Matroid theory, matroids, a graphic matroid (also called a cycle matroid or polygon matroid) is a matroid whose independent sets are the tree (graph theory), forests in a given finite undirected graph. The dual matr ...

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 tree In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is no ...

s, to be independent. The wheel ''W''₆ supplied a counterexample to a conjecture of

Paul Erdős Paul Erdős ( ; 26March 191320September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in discrete mathematics, g ...

Ramsey theory Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of the mathematical field of combinatorics that focuses on the appearance of order in a substructure given a structure of a known size. Problems in R ...

: 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 In mathematics, Paley graphs are undirected graphs constructed from the members of a suitable finite field by connecting pairs of elements that differ by a quadratic residue. The Paley graphs form an infinite family of conference graphs, which yiel ...

nor its complement contains a copy of ''K''₄.

References

{{reflist Parametric families of graphs Planar graphs