Almost all trees are almost graceful |
| |
Authors: | Anna Adamaszek Peter Allen Codru Grosu Jan Hladký |
| |
Institution: | Anna Adamaszek,Peter Allen,Codruţ Grosu,Jan Hladký |
| |
Abstract: | The Graceful Tree Conjecture of Rosa from 1967 asserts that the vertices of each tree T of order n can be injectively labeled by using the numbers {1,2,…,n} in such a way that the absolute differences induced on the edges are pairwise distinct. We prove the following relaxation of the conjecture for each γ>0 and for all n>n0(γ). Suppose that (i) the maximum degree of T is bounded by ), and (ii) the vertex labels are chosen from the set {1,2,…,?(1+γ)n?}. Then there is an injective labeling of V(T) such that the absolute differences on the edges are pairwise distinct. In particular, asymptotically almost all trees on n vertices admit such a labeling. The proof proceeds by showing that a certain very natural randomized algorithm produces a desired labeling with high probability. |
| |
Keywords: | extremal graph theory graceful tree labelling tree |
|
|