Mathematics – General Mathematics
Scientific paper
2005-03-23
Mathematics
General Mathematics
36 pages. A thorough rivision is carried out, adding clarity at many places
Scientific paper
A method to obtain all possible graceful spanning trees in a complete graph is proposed. An algorithm to generate all the labeled spanning trees in a complete graph is developed and modified to generate all graceful spanning trees. The count of all possible graceful graphs in a complete graph is obtained. An upper bound on the count of gracefully labeled trees in a complete graph is obtained. We settle Graceful Tree Conjecture in the affirmative in two ways: 1) We show that all trees can be gracefully labeled by assigning the lowest label 1 to the so called special vertices of trees, i.e. prependant vertices or pendant vertices adjacent to prependant vertices. 2) We establish the existence of graceful labeling for all trees by associating distinct lattice paths with trees and by showing the existence of a lattice path for a tree of each isomorphism type by showing how to construct a lattice path recursively by starting from the lattice path for its pendant vertex deleted subtree, which is assumed to exists by induction, and carrying out appropriate modification of this lattice path. Lastly, we discuss an algorithm to find arbitrarily degree constrained graceful spanning tree and propose some problems for further investigation.
No associations
LandOfFree
On Gracefully Labeling Trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On Gracefully Labeling Trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Gracefully Labeling Trees will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-135099