Abstract: The Graceful Tree Conjecture of Rosa from 1967 asserts that the vertices of each tree T of order n can be injectively labelled 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 c>0 and for all n>n_0(c). 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+c)n}. Then there is an injective labelling 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 labelling. As a consequence, for any such tree T we can pack (2+2c)n-1 copies of T into the complete graph of order (2+2c)n-1 cyclically. This proves an approximate version of the Ringel-Kotzig conjecture (which asserts the existence of a cyclic packing of 2n-1 copies of any T into the complete graph of order 2n-1) for these trees. The proof proceeds by showing that a certain very natural randomized algorithm produces a desired labelling with high probability.
Recommendations
- scientific article; zbMATH DE number 17650
- scientific article; zbMATH DE number 3849284
- scientific article; zbMATH DE number 1925192
- scientific article; zbMATH DE number 790410
- scientific article; zbMATH DE number 1789795
- scientific article; zbMATH DE number 568853
- All trees of diameter five are graceful
- A survey of graceful trees
- Gracefulness of a family of rooted trees
- All banana trees are graceful
Cites work
- A blow-up lemma for approximate decompositions
- All banana trees are graceful
- An approximate version of the tree packing conjecture
- Differential equations for random processes and random graphs
- scientific article; zbMATH DE number 3670474 (Why is no real title available?)
- scientific article; zbMATH DE number 3698968 (Why is no real title available?)
- scientific article; zbMATH DE number 3762115 (Why is no real title available?)
- scientific article; zbMATH DE number 3458691 (Why is no real title available?)
- scientific article; zbMATH DE number 1540669 (Why is no real title available?)
- scientific article; zbMATH DE number 3308125 (Why is no real title available?)
- Infinitely many equivalent versions of the graceful tree conjecture
- On Additive Bases and Harmonious Graphs
- On the maximum degree in a random tree
- Operations of interlaced trees and graceful trees
- Optimal packings of bounded degree trees
- Packing degenerate graphs
- Packing minor-closed families of graphs into complete graphs
- Packing spanning graphs from separable families
- Packing trees of unbounded degrees in random graphs
- Probability Inequalities for Sums of Bounded Random Variables
- Relaxed graceful labellings of trees
Cited in
(12)- Embedding rainbow trees with applications to graph labelling and decomposition
- A proof of Ringel's conjecture
- Optimal packings of bounded degree trees
- Packing degenerate graphs
- scientific article; zbMATH DE number 17650 (Why is no real title available?)
- Bipartite labeling of trees with maximum degree three
- A rainbow blow-up lemma for almost optimally bounded edge-colourings
- Recent developments on gracefulness of graphs. A survey complemented with chessboard representations
- Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
- Graph and hypergraph packing
- Ringel's tree packing conjecture in quasirandom graphs
- Counting graceful labelings of trees: a theoretical and empirical study
This page was built for publication: Almost all trees are almost graceful
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5128748)
