mathworld.wolfram.com

Wheel Graph -- from Wolfram MathWorld

  • ️Weisstein, Eric W.
Algebra Applied Mathematics Calculus and Analysis Discrete Mathematics Foundations of Mathematics Geometry History and Terminology Number Theory Probability and Statistics Recreational Mathematics Topology Alphabetical Index New in MathWorld

WheelGraphs

As defined in this work, a wheel graph W_n of order n, sometimes simply called an n-wheel (Harary 1994, p. 46; Pemmaraju and Skiena 2003, p. 248; Tutte 2005, p. 78), is a graph that contains a cycle of order n-1 and for which every graph vertex in the cycle is connected to one other graph vertex known as the hub. The edges of a wheel which include the hub are called spokes (Skiena 1990, p. 146). The wheel W_n can be defined as the graph join K_1+C_(n-1), where K_1 is the singleton graph and C_n is the cycle graph, making it a (n,1)-cone graph. Wheel graphs of order 4 to 8 are illustrated above in a number of embeddings.

Note that some authors (e.g., Gallian 2007) adopt an alternate convention in which W_n denotes the wheel graph on n+1 nodes.

The tetrahedral graph (i.e., K_4) is isomorphic to W_4, and W_5 is isomorphic to the complete tripartite graph K_(1,2,2). In general, the n-wheel graph is the skeleton of an (n-1)-pyramid.

The wheel graph W_n is isomorphic to the Jahangir graph J_(1,n-1).

W_5 is one of the two graphs obtained by removing two edges from the pentatope graph K_5, the other being the house X graph.

W_5 is a quasi-regular graph.

Wheel graphs are graceful (Frucht 1979), self-dual, pancyclic, and dominating unique.

The wheel graph W_n has graph dimension 2 for n=7 (and hence is unit-distance) and dimension 3 otherwise (and hence not unit-distance) (Erdős et al. 1965, Buckley and Harary 1988).

Wheel graphs can be constructed in the Wolfram Language using WheelGraph[n]. Precomputed properties of a number of wheel graphs are available via GraphData[{"Wheel", n}].

WheelGraphCycles4

WheelGraphCycles5

The number of graph cycles in the wheel graph W_n is given by n^2-3n+3, or 7, 13, 21, 31, 43, 57, ... (OEIS A002061) for n=4, 5, ....

In a wheel graph, the hub has degree n-1, and other nodes have degree 3. Wheel graphs are 3-connected. W_4=K_4, where K_4 is the complete graph of order four. The chromatic number of W_n is

chi(W_n)={3 for n odd; 4 for n even.

(1)

The wheel graph W_n has chromatic polynomial

pi(x)=x[(x-2)^(n-1)-(-1)^n(x-2)].

(2)

See also

Complete Graph, Cone Graph, Dipyramidal Graph, Gear Graph, Helm Graph, Hub, Jahangir Graph, Ladder Graph, Pyramid, Spoke Graph, Tutte's Wheel Theorem, Web Graph, Wheel Complement Graph

Explore with Wolfram|Alpha

References

Brandstädt, A.; Le, V. B.; and Spinrad, J. P. Graph Classes: A Survey. Philadelphia, PA: SIAM, p. 19, 1987.Buckley, F. and Harary, F. "On the Euclidean Dimension of a Wheel." Graphs and Combin. 4, 23-30, 1988.Frucht, R. "Graceful Numbering of Wheels and Related Graphs." Ann. New York Acad. Sci. 319, 219-229, 1979.Erdős, P.; Harary, F.; and Tutte, W. T. "On the Dimension of a Graph." Mathematika 12, 118-122, 1965.Gallian, J. "Dynamic Survey of Graph Labeling." Elec. J. Combin. DS6. Dec. 21, 2018. https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, p. 46, 1994.Pemmaraju, S. and Skiena, S. "Cycles, Stars, and Wheels." §6.2.4 in Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematica. Cambridge, England: Cambridge University Press, pp. 248-249, 2003.Saaty, T. L. and Kainen, P. C. The Four-Color Problem: Assaults and Conquest. New York: Dover, p. 148, 1986.Skiena, S. "Cycles, Stars, and Wheels." §4.2.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 91 and 144-147, 1990.Sloane, N. J. A. Sequence A002061/M2638 in "The On-Line Encyclopedia of Integer Sequences."Tutte, W. T. Graph Theory. Cambridge, England: Cambridge University Press, 2005.

Referenced on Wolfram|Alpha

Wheel Graph

Cite this as:

Weisstein, Eric W. "Wheel Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/WheelGraph.html

Subject classifications