Graceful labeling construction for some special tree graph using adjacency matrix

Nikson Simarmata, Ikhlas Pratama Sandy, Kiki A. Sugeng


In 1967, Rosa introduced β − labeling which was then popularized by Golomb under the name graceful. Graceful labeling on a graph G is an injective function f : V(G)→{0, 1, 2, …, |E(G)|} such that, when each edge uv ∈ E(G) is assigned the label |f(u)−f(v)| the resulting edge labels are distinct. If graph G has graceful labeling then G is called a graceful graph. Rosa also introduced α − labeling on graph G which is a graceful labeling f with an additional condition that there is λ ∈ {1, 2, …, |E(G)|} so that for every edge uv ∈ E(G) where f(u)<f(v) then f(u)≤λ < f(v). This paper gives a new approach to showing a graph is admitted α − labeling using an adjacency matrix. Then this construction will be used to construct graceful labeling for the superstar graph. Moreover, we give a graceful labeling construction for a super-rooted tree graph.


graceful labeling, α-labeling, star graph, superstar graph, adjacency matrix

Full Text:




L. Brankovic, M. J. Reynolds, Computer search for graceful labeling: a survey, Electron. J. Graph Theory Appl. 10 (1) (2022), 319–336.

C. M. Cavalier, Graceful labeling, Thesis, University of South Carolina (2009).

G. Chartrand, and P. Zhang, A first course in graph theory, McGraw-Hill Higher Education (2012).

J. A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. (2021), DS6.

S.Ghosh, On certain classes of graceful lobsters, Ars Combin. 136 (2018), 67–96.

S. M. Lee, E. Schmeichel, and S. C. Shee. On felicitous graphs. Discrete Math. 93 (1991), 201–209.

R. N. Pakpahan, I. Mursidah, I. Novitasari, and K. A. Sugeng, Graceful labeling for some supercaterpillar graphs, AIP Conference Proceedings 1862 (1), 030121 (2107).

A. Rosa, On certain valuations of the vertices of a graph, Theory of Graphs (Internat. Symposium, Rome, July 1966), Gordon and Breach, N. Y. and Dunod Paris (1967), 349-355.

G. Sethuraman and J. Jesintha, A new class of graceful lobsters, J. Combin. Math. Combin. Comput. 67 (2008), 99–109.

I. N. Suparta and I Dewa M. Agus Ariawan, Expanding graceful trees, Electron. J. Graph Theory Appl. 8 (2) (2020), 217–232.

I.N. Suparta and D. M. A. Ariawan, Some methods for constructing some classes of graceful uniform trees, Indonesian Journal of Combinatorics 2 (2) (2018), 123–135.


  • There are currently no refbacks.

ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats