Combinatorics and Graph Theory


Graceful Labeling for Trees

Authors: Dhananjay P. Mehendale

We define so called n-delta lattice containing (n-1) lattice points in first (topmost) row, (n-2) lattice points in second row, and so on. Each time the count of lattice points decreases by unity as we move down by one row till we reach the last (bottommost) row containing single lattice point. We label these lattice points in two different ways and obtain two different labeled lattices. In the first kind of labeling we associate vertex pairs in a particular way as labels for points of the lattice and so call it edge-labeled n-delta lattice. In the second kind of labeling we associate integers as labels with lattice points in each row to indicate the position of that lattice point in the row and so call it position-labeled n-delta lattice. This defining of position-labeled n-delta lattice enables us to associate a lexicographic ordering with lattice paths. We define distinct as well as different lattice paths and further see that for proving graceful tree conjecture one needs to show that the count of distinct lattice paths corresponding to trees in the edge-labeled n-delta lattice is same as the count of nonisomorphic trees with n vertices. We verify this for some (small) values of n. We further see that existence of graceful labeling for an unlabeled tree with n vertices follows from the existence of a lattice path representing this same tree in the edge-labeled n-delta lattice. It is possible to generate all (n, n-1)-trees from all (n-1, n-2)-trees by attaching an edge that emerges from each of the inequivalent vertices of (n-1, n-2)-trees and entering in the new vertex taken outside. We show that extending all lattice paths by adding a lattice point in the paths sitting in the sub-lattice of n-delta lattice in all possible ways is same as the above mentioned generation of trees from lower trees.

Comments: 15 Pages. Rivised

Download: PDF

Submission history

[v1] 2013-10-25 13:12:48
[v2] 2013-11-12 01:52:44

Unique-IP document downloads: 878 times is a pre-print repository rather than a journal. Articles hosted may not yet have been verified by peer-review and should be treated as preliminary. In particular, anything that appears to include financial or legal advice or proposed medical treatments should be treated with due caution. will not be responsible for any consequences of actions that result from any form of use of any documents on this website.

Add your own feedback and questions here:
You are equally welcome to be positive or negative about any paper but please be polite. If you are being critical you must mention at least one specific error, otherwise your comment will be deleted as unhelpful.

comments powered by Disqus