تسجيل الدخول

تسجيل

Wheel Graph

المؤلف:  Brandstädt, A.; Le, V. B.; and Spinrad, J. P.

المصدر:  Graph Classes: A Survey. Philadelphia, PA: SIAM

الجزء والصفحة:  ...

23-3-2022

4505

Wheel Graph

 

As defined in this work, a wheel graph  of order , sometimes simply called an -wheel (Harary 1994, p. 46; Pemmaraju and Skiena 2003, p. 248; Tutte 2005, p. 78), is a graph that contains a cycle of order  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  can be defined as the graph join , where  is the singleton graph and  is the cycle graph, making it a -cone graph.

Note that some authors (e.g., Gallian 2007) adopt the alternate convention that  denotes the wheel graph on  nodes.

The tetrahedral graph (i.e., ) is isomorphic to , and  is isomorphic to the complete tripartite graph . In general, the -wheel graph is the skeleton of an -pyramid.

The wheel graph  is isomorphic to the Jahangir graph .

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

Wheel graphs are graceful (Frucht 1979).

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

Any wheel graph is a self-dual graph.

Wheel graphs can be constructed in the Wolfram Language using WheelGraph[n]. Precomputed properties of a number of wheel graphs are available via GraphData[{" src="https://mathworld.wolfram.com/images/equations/WheelGraph/Inline24.svg" style="height:22px; width:6px" />"Wheel", n}" src="https://mathworld.wolfram.com/images/equations/WheelGraph/Inline25.svg" style="height:22px; width:6px" />].

The number of graph cycles in the wheel graph  is given by , or 7, 13, 21, 31, 43, 57, ... (OEIS A002061) for , 5, ....

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

{3 for n odd; 4 for n even. " src="https://mathworld.wolfram.com/images/equations/WheelGraph/NumberedEquation1.svg" style="height:53px; width:177px" />

(1)

The wheel graph  has chromatic polynomial

(2)

---

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.