Nicely graceful labellings of tadpoles

Articles in Press

Document Type : Original paper

Authors

1 Department of Mathematics, Universitas Pendidikan Ganesha, Bali, Indonesia

2 Department of Applied Mathematics and Informatics, Technical University of Koˇsice, Slovak

3 Department of Mathematical Science, RMIT University, Melbourne, Australia

4 Department of Applied Mathematics and Informatics, Technical University of Košice, Slovak

5 Department of Informatics, Universitas Pendidikan Ganesha, Bali, Indonesia

Abstract

A vertex-labelling $f:V\to \{0,1,\ldots, |E|\}$  for a finite undirected simple graph $G(V, E)$ is called graceful  if $f$ is injective and satisfies the additional property that $\{|f(u)-f(v)|: \text{for every edge} uv\in E\}=\{1,2,\ldots,|E|\}$, where $|E|$ is the number of edges in $G$. Let $M$ be a maximum matching in $G$ and let $f$ also satisfy the property that $f(u)+f(v)=W$ for every $uv\in M$, where $W$ is a constant; then the labelling $f$ is called nicely graceful.  Furthermore,  if  $M$ is a perfect matching in $G$, then $f$ is said to be strongly graceful. In this paper, we investigate nicely and strongly graceful labellings of cycles and tadpoles that are obtained from a cycle by attaching a path to a vertex of the cycle. This leads to a complete characterisation of nicely graceful cycles and strongly graceful tadpoles.

Keywords

Main Subjects

References

[1] J.S. Bagga, L.P. Fotso, M.P. Biatch’, and S. Arumugam, New classes of graceful unicyclic graphs, Electron. Notes Discrete Math. 48 (2015), 27–32. https://doi.org/10.1016/j.endm.2015.05.005
[2] C. Barrientos, Graceful graphs with pendant edges, Australas. J. Combin. 33 (2005), 99–108.
[3] M.P. Biatch’, J.S. Bagga, and S. Arumugam, A survey and a new class of graceful unicylic graphs, AKCE Int. J. Graphs Comb. 17 (2020), no. 2, 673–678. https://doi.org/10.1080/09728600.2020.1832853
[4] H.J. Broersma and C. Hoede, Another equivalent of the graceful tree conjecture, Ars Combin. 51 (1999), 183–192.
[5] R. Diestel, Graph Theory, Graduate Texts in Mathematics, Springer Berlin, Heidelberg, 2017.
[6] K. Eshghi, Introduction to Graceful Graphs, Sharif University of Technology, Tehran, Iran, 2002.
[7] J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. (2024), #DS6.
[8] D. Morgan, All lobsters with perfect matchings are graceful, Electron. Notes Discrete Math. 11 (2002), 503–508. https://doi.org/10.1016/S1571-0653(04)00095-2
[9] A. Rosa, On certain valuations of the vertices of a graph, Theory of Graphs, Proc. Internat. Sympos. Rome 1966, Gordon and Breach, New York, 1967, pp. 349–355.
[10] R. Sivaraman, Graceful graphs and its applications, Int. J. Current Research 8 (2016), no. 11, 41062–41067.
[11] A. Solairaju and S. Malathi, Graceful labeling of graphs related to circuits of length 4, Int. J. Comput. Appl. 105 (2014), no. 1, 29–32.
[12] I N. Suparta and W.W.P. Dani, Graceful cycles with perfect matching are strongly graceful, AIP Conf. Proc. 2614 (2023), no. 1, 040064. https://doi.org/10.1063/5.0126789
[13] M. Truszczy´nski, Graceful unicyclic graphs, Demonstr. Math. 17 (1984), no. 2, 377–388. https://doi.org/10.1515/dema-1984-0211
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 03 May 2026

Files

Share

How to cite

Statistics