TOPICS
Search

Helm Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
HelmGraph

The helm graph H_n is the graph obtained from an n-wheel graph by adjoining a pendant edge at each node of the cycle.

Helm graphs are graceful (Gallian 2018), with the odd case of n established by Koh et al. 1980 and the even case by Ayel and Favaron (1984). The helm graph H_n is perfect only for n=3 and even n.

Precomputed properties of helm graphs are available in the Wolfram Language using GraphData[{"Helm", {n, k}}].

The n-Helm graph has chromatic polynomial, independence polynomial, and matching polynomial given by

pi_n(z)=z[(1-z)^n(z-2)+(z-2)^n(z-1)^n]
(1)
I_n(x)=2^(-n)[2^nx(+x+1)^n+(x-sqrt((x+1)(5x+1))+1)^n+(x+sqrt((x+1)(5x+1))+1)^n]
(2)
mu(x)=((n+s)x(-1-s+x^2)^n-(n-s)x(-1+s+x^2)^n)/(2^ns),
(3)

where s=sqrt(1-6x^2+x^4). These correspond to recurrence equations (together with for the rank polynomial) of

pi_n(z)=(z-3)(z-1)pi_(n-1)(z)+(z-2)(z-1)^2pi_(n-2)(z)
(4)
I_n(x)=2(x+1)I_(n-1)(x)-(x+1)I_(n-2)(x)-x(x+1)^2I_(n-3)(x)
(5)
mu_n(x)=2(x-1)(x+1)mu_(n-1)(x)-(x^4+1)mu_(n-2)(x)+2(x-1)(x+1)x^2mu_(n-3)(x)-x^4mu_(n-4)(x)
(6)
R_n(x,y)=(x+1)(xy+4x+1)R_(n-1)(x,y)-x(2x+1)(x+1)^2(y+2)R_(n-2)(x,y)+x^2(x+1)^4(y+1)R_(n-3)(x,y).
(7)

See also

Crossed Prism Graph, Cycle Graph, Flower Graph, Möbius Ladder, Prism Graph, Web Graph, Wheel Graph

Explore with Wolfram|Alpha

References

Ayel, J. and Favaron, O. "Helms Are Graceful. In Progress in Graph Theory (Waterloo, Ont., 1982). Toronto: Academic Press, pp. 89-92, 1984.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.Koh, K. M.; Rogers, D. G.; and Yap, K. Y. "Graceful Graphs: Some Further Results and Problems." Congr. Numer. 29, 559-571, 1980.Seoud, M. Z. and Youssef, M. A. "Harmonious Labelling of Helms and Related Graphs." Unpublished work. Jan. 2017. http://dx.doi.org/10.13140/RG.2.2.11041.61282.

Referenced on Wolfram|Alpha

Helm Graph

Cite this as:

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

Subject classifications