2011 | OriginalPaper | Chapter
On Graceful Labelings of Trees
(Extended Abstract)
Authors : Sourabh Aryabhatta, Tonmoy Guha Roy, Md. Mohsin Uddin, Md. Saidur Rahman
Published in: WALCOM: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
A tree is a connected acyclic graph. A tree of
n
vertices is said to be graceful if the vertices can be assigned the labels { 0, 1, 2, ...,
n
− 1} such that the absolute value of the differences in vertex labels between neighboring vertices generate the set consisting distinct values { 1, 2, 3, ...,
n
− 1}. Ringel-Kotzig conjectured that all trees are graceful. In this paper we give a partial solution of the conjecture by proving that two large subclasses of trees are graceful.