Characterizations of kites as graceful graphs

Miroslav Haviar; Katarina Kotuľová

doi:10.56754/0719-0646.2603.367

DOI:

https://doi.org/10.56754/0719-0646.2603.367

Abstract

We introduce and study an infinite family of graceful graphs, which we call kites. The kites are graphs where a path is joined with a graph "forming" a kite. We study and characterize three classes of the kites: kites formed by cycles known to be graceful, fan kites and lantern kites. Beside showing in a transparent way that all these graphs are graceful, we provide characterizations of these graphs among all simple graphs via three tools: via Sheppard's labelling sequences introduced in the 1970s and via labelling relations and graph chessboards. The latter are relatively new tools for the study of graceful graphs introduced by Haviar and Iva\v ska in 2015. The labelling relations are closely related to Sheppard's labelling sequences while the graph chessboards provide a~nice visualization of the graceful labellings.

Keywords

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

Mathematics Subject Classification:

05C78

Miroslav Haviar Department of Mathematics, Faculty of Natural Sciences, Matej Bel University, Tajovského 40, 974 01 Banská Bystrica, Slovakia - Mathematical Institute, Slovak Academy of Sciences, Ďumbierska 1, 974 11 Banská Bystrica, Slovakia - Department of Mathematics and Applied Mathematics, University of Johannesburg, PO Box 524, Auckland Park, 2006 South Africa. https://orcid.org/0000-0002-9721-152X
Katarina Kotuľová Department of Mathematics, Faculty of Natural Sciences, Matej Bel University, Tajovského 40, 974 01 Banská Bystrica, Slovakia. https://orcid.org/0009-0005-1303-5274

Pages: 367–386
Date Published: 2024-10-01
Vol. 26 No. 3 (2024)

J. A. Gallian, “A dynamic survey of graph labeling,” Electron. J. Combin., vol. 5, pp. Dynamic Survey 6, 43, 1998.

M. Haviar and S. Kurtulík, “A new class of graceful graphs: k-enriched fan graphs and their characterisations,” Cubo, vol. 23, no. 2, pp. 313–331, 2021.

M. Haviar and M. Ivaška, Vertex labellings of simple graphs, ser. Research and Exposition in Mathematics. Heldermann Verlag, Lemgo, 2015, vol. 34.

K. M. Koh, D. G. Rogers, H. K. Teo, and K. Y. Yap, “Graceful graphs: some further results and problems,” Congr. Numer., vol. 29, pp. 559–571, 1980.

K. Kotuľová, “Vertex labellings of simple graphs,” M.Sc. thesis, 50 pp., M. Bel University, Banská Bystrica, 2023.

S. Kurtulík, “New descriptions of certain classes of graceful graphs,” Acta Univ. M. Belii Ser. Math., vol. 28, pp. 67–84, 2020.

A. Rosa, “O cyklických rozkladoch kompletného grafu,” (Slovak) [On cyclic decompositions of the complete graph], Ph.D. dissertation, Ceskoslovenská akadémia vied, Bratislava, 1965, Available: https://archive.org/details/o-cyklickych-rozkladoch-kompletneho-garfu/

mode/2up.

A. Rosa, “On certain valuations of the vertices of a graph,” in Theory of Graphs (Internat. Sympos., Rome, 1966). Gordon & Breach, New York, 1967, pp. 349–355.

D. A. Sheppard, “The factorial representation of balanced labelled graphs,” Discrete Math., vol. 15, no. 4, pp. 379–388, 1976, doi: 10.1016/0012-365X(76)90051-0.

M. Truszczyński, “Graceful unicyclic graphs,” Demonstratio Math., vol. 17, no. 2, pp. 377–387, 1984.