Helm Graph

 

 

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

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

Precomputed properties of helm graphs are available in the Wolfram Language using GraphData[{" src="https://mathworld.wolfram.com/images/equations/HelmGraph/Inline7.svg" style="height:22px; width:6px" />"Helm", {" src="https://mathworld.wolfram.com/images/equations/HelmGraph/Inline8.svg" style="height:22px; width:6px" />n, k}" src="https://mathworld.wolfram.com/images/equations/HelmGraph/Inline9.svg" style="height:22px; width:6px" />}" src="https://mathworld.wolfram.com/images/equations/HelmGraph/Inline10.svg" style="height:22px; width:6px" />].

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

			(1)
			(2)
			(3)

where . These correspond to recurrence equations (together with for the rank polynomial) of

			(4)
			(5)
			(6)
			(7)

---

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.

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength