Generating Graceful Trees from Caterpillars by Recursive Attachment

A graceful labeling of a graph G with n   edges is an injection f:V(G)→{0,1,2,⋯,n}f:V(G)→{0,1,2,⋯,n} with the property that the resulting edge labels are also distinct, where an edge incident with vertices u and v   is assigned the label |f(u)−f(v)||f(u)−f(v)|. A graph which admits a graceful labeling is called a graceful graph. In this paper, inspired by Koh [K.M. Koh, D.G. Rogers and T. Tan, Two theorems on graceful trees, Discrete Math., 25 (1979), 141–148] method, which combines a known graceful trees to obtain a larger graceful trees, we introduced a new method of combining graceful trees called recursive attachment method, and we show that the recursively attached tree Ti=Ti−1⊕TAi−1Ti=Ti−1⊕TAi−1 is graceful, for i≥1i≥1, where T0T0 is a base tree which is taken as a caterpillar and TAi−1TAi−1 is an attachment tree which taken as any caterpillar. Here Ti−1⊕TAi−1Ti−1⊕TAi−1 represents a tree obtained by attaching a copy of TAi−1TAi−1 at each vertex of degree at least two in Ti−1Ti−1, for i≥1i≥1. Consequently the graceful tree conjecture is true for every recursively attached caterpillar tree TiTi, for i≥1i≥1.