CORONA PRODUCT OF GRACEFUL TREES

ABSTRACT. A function f is called graceful labeling of a graph G with m edges,
if f is an injective function from V (G) to {0, 1, 2, . . . , m} such that, when every
edge uv is assigned the edge label |f(u) − f(v)|, then the resulting edge labels
are distinct. A graph which admits graceful labeling is called a graceful graph.
The fifty-year old Graceful Tree Conjecture, due to Rosa, Ringel and Kotzig
states that every tree is graceful. Let G and H be two graphs and let n be the
order of G. The corona product, or simply the corona, of graphs G and H is
the graph G
H obtained by taking one copy of G and n copies of H and thenjoining by an edge the ith vertex of G to every vertex in the ith copy of H. Notethat when G is a tree and H ∼= K1, the corona GK1 is also a tree. In this note,we prove that if T is a graceful tree, then the corona T
K1 is also graceful.