Generating Graceful Trees from Caterpillars by Recursive Attachment

Abstract A graceful labeling of a graph G with n edges is an injection 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 ) | . 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 T i = T i − 1 ⊕ T A i − 1 is graceful, for i ≥ 1 , where T 0 is a base tree which is taken as a caterpillar and T A i − 1 is an attachment tree which taken as any caterpillar. Here T i − 1 ⊕ T A i − 1 represents a tree obtained by attaching a copy of T A i − 1 at each vertex of degree at least two in T i − 1 , for i ≥ 1 . Consequently the graceful tree conjecture is true for every recursively attached caterpillar tree T i , for i ≥ 1 .