Almost all trees are almost graceful. Issue 4 (19th February 2020)

• Record Type: Journal Article
• Authors: Adamaszek, Anna; Allen, Peter; Grosu, Codruţ; Hladký, Jan
• Is Part Of: Random structures & algorithms. Volume 56:Issue 4(2020)
• Page Start: 948
• Page End: 987
• Publication Date: 2020-02-19
• Subjects: extremal graph theory -- graceful tree labelling -- tree; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20906
• Languages: English
• ISSNs: 1042-9832

Abstract

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 > n 0 ( γ ). Suppose that (i) the maximum degree of T is bounded by O γ ( n / log n ), 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.