Characterizations of kites as graceful graphs II

Miroslav Haviar; Jakub Ivan

doi:10.56754/0719-0646.2803.523

Authors

Miroslav Haviar Department of Mathematics, Faculty of Natural Sciences, Matej Bel University, Banská Bystrica, Slovakia; Mathematical Institute, Slovak Academy of Sciences, Bratislava, Slovakia; Department of Mathematics and Applied Mathematics, University of Johannesburg, Auckland Park, South Africa https://orcid.org/0000-0002-9721-152X
Jakub Ivan Department of Mathematics, Faculty of Natural Sciences, Matej Bel University, Banská Bystrica, Slovakia https://orcid.org/0009-0005-0435-736X

MSC:

05C78

DOI:

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

Keywords:

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

Abstract

Vertex and edge labellings have played a significant role in the study of graphs since the foundation of the theory of graph labellings in the 1960s. This paper is focused on the specific case of vertex labellings called graceful labellings. It is a companion to a paper published in this journal in 2024, in which we characterized “kites” formed by the cycles known to be graceful. It was left there as a possible further research direction to characterize the remaining kites formed by the non-graceful cycles. The present paper completes this task. The kites formed by the non-graceful cycles are characterized among all simple graphs via Sheppard’s labelling sequences, and via labelling relations and graph chessboards. While the labelling relations are rather closely related to the labelling sequences, the graph chessboards provide a nice visualization of the gracefulness of the graphs they represent.

References

[1] J. A. Gallian, “A dynamic survey of graph labeling,” The Electronic Journal of Combinatorics, 2025, Art. ID #DS6.

[2] S. W. Golomb, “How to number a graph,” in Graph Theory and Computing. Academic Press, 1972, pp. 23–37, doi: 10.1016/B978-1-4832-3187-7.50008-8.

[3] M. Haviar and S. Kurtulík, “A new class of graceful graphs: k-enriched fan graphs,” Cubo, vol. 23, no. 2, pp. 313–331, 2021, doi: 10.4067/S0719-06462021000200313.

[4] M. Haviar and M. Ivaška, Vertex labellings of simple graphs, ser. Res. Expo. Math. Lemgo: Heldermann Verlag, 2015, vol. 34.

[5] M. Haviar and K. Kotuľová, “Characterizations of kites as graceful graphs,” Cubo, vol. 26, no. 3, pp. 367–386, 2024, doi: 10.56754/0719-0646.2603.367.

[6] J. Ivan, “Graceful labellings of graphs,” BSc. Thesis, M. Bel University, Banská Bystrica, Slovakia, 2025.

[7] K. M. Koh, D. G. Rogers, P. Y. Lee, and C. W. Toh, “On graceful graphs. V: Unions of graphs with one vertex in common,” Nanta Math., vol. 12, pp. 133–136, 1979.

[8] A. Rosa, “O cyklických rozkladoch kompletného grafu,” Ph.D. dissertation, Československá akadémia vied, Bratislava, Czechoslovakia, 1965, [On cyclic decompositions of the complete graph] (in Slovak).

[9] A. Rosa, “On certain valuations of the vertices of a graph,” in Theory of Graphs. Gordon and Breach, 1967, pp. 349–355.

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

[11] M. Truszczyński, “Graceful unicyclic graphs,” Demonstr. Math., vol. 17, pp. 377–387, 1984.