A new class of graceful graphs: \(k\)-enriched fan graphs and their characterisations

M. Haviar; S. Kurtulík

doi:10.4067/S0719-06462021000200313

DOI:

https://doi.org/10.4067/S0719-06462021000200313

Abstract

The Graceful Tree Conjecture stated by Rosa in the mid 1960s says that every tree can be gracefully labelled. It is one of the best known open problems in Graph Theory. The conjecture has caused a great interest in the study of gracefulness of simple graphs and has led to many new contributions to the list of graceful graphs. However, it has to be acknowledged that not much is known about the structure of graceful graphs after 55 years.

Our paper adds an infinite family of classes of graceful graphs to the list of known simple graceful graphs. We introduce classes of \(k\)-enriched fan graphs \(kF_n\) for all integers \(k, n\ge 2\) and we prove that these graphs are graceful. Moreover, we provide characterizations of the \(k\)-enriched fan graphs \(kF_n\) among all simple graphs via Sheppard's labelling sequences introduced in the 1970s, as well as via labelling relations and graph chessboards. These last approaches are new tools for the study of graceful graphs introduced by Haviar and Ivaška in 2015. The labelling relations are closely related to Sheppard's labelling sequences while the graph chessboards provide a nice visualization of graceful labellings. We close our paper with an open problem concerning another infinite family of extended fan graphs.

Keywords

graph , graceful labelling , graph chessboard , labelling sequence , labelling relation

M. Haviar Department of Mathematics, Faculty of Natural Sciences, Matej Bel University, Banská Bystrica, Slovakia – Mathematical Institute, Slovak Academy of Sciences, Bratislava, Slovakia.
S. Kurtulík Department of Mathematics, Faculty of Natural Sciences, Matej Bel University, Banská Bystrica, Slovakia.

Pages: 313–331
Date Published: 2021-08-01
Vol. 23 No. 2 (2021)

S. Amutha and M. Uma Devi, “Super Graceful Labeling for Some Families of Fan Graphs”, Journal of Computer and Mathematical Sciences, vol. 10, no. 8, pp. 1551–1562, 2019.

J. A. Gallian, “A Dynamic Survey of Graph Labeling”, Electron. J. Combin., # DS6, Twenty- second edition, 2019.

M. Gardner, “Mathematical Games: The graceful graphs of Solomon Golomb”, Sci. Am., vol. 226, no. 23, pp. 108–112, 1972.

S. W. Golomb, “How to number a graph”, In: Graph Theory and Computing, pp. 23–37, Academic Press, 1972.

M. Haviar and M. Ivaška, Vertex Labellings of Simple Graphs. Research and Exposition in Mathematics, vol. 34, Lemgo, Germany: Heldermann-Verlag, 2015.

P. HrnÄiar and A. Haviar, “All trees of diameter five are graceful”, Discrete Math., vol. 233, no. 1-3, pp. 133–150, 2001.

M. Ivaška, “Chessboard Representations and Computer Programs for Graceful Labelings of Trees”, Student Competition Å VOÄŒ, M. Bel University, Banská Bystrica, 2009.

S. Kurtulík, “Graceful labellings of graphs”, MSc. thesis, 52 pp., Department of Mathematics, M. Bel University, Banská Bystrica, 2020.

A. Rosa, “O cyklických rozkladoch kompletného grafu” [On cyclic decompositions of the complete graph], PhD thesis (in Slovak), ÄŒeskoslovenská akadémia vied, Bratislava, 1965.

A. Rosa, “On certain valuations of the vertices of a graph”, In: Theory of Graphs (Internat. Symposium, Rome, July 1966), pp. 349–355, New York: Gordon and Breach, 1967.

D. A. Sheppard, “The factorial representation of major balanced labelled graphs”, Discrete Math., vol. 15, no. 4, pp. 379–388, 1976.

K. Xu, X. Li and S. Klavžar, “On graphs with largest possible game domination number”, Discrete Math., vol. 341, no. 6, pp. 1768–1777, 2018.