Header menu link for other important links
X
Generating Graceful Trees from Caterpillars by Recursive Attachment
G. Sethuraman,
Published in Elsevier B.V.
2016
Volume: 53
   
Pages: 133 - 147
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 Ti=Ti−1⊕TAi−1 is graceful, for i≥1, where T0 is a base tree which is taken as a caterpillar and TAi−1 is an attachment tree which taken as any caterpillar. Here Ti−1⊕TAi−1 represents a tree obtained by attaching a copy of TAi−1 at each vertex of degree at least two in Ti−1, for i≥1. Consequently the graceful tree conjecture is true for every recursively attached caterpillar tree Ti, for i≥1. © 2016 Elsevier B.V.
About the journal
JournalData powered by TypesetElectronic Notes in Discrete Mathematics
PublisherData powered by TypesetElsevier B.V.
ISSN15710653