Almost all trees are almost graceful
| Autor: | Adamaszek, Anna, Allen, Peter, Grosu, Codrut, Hladky, Jan |
|---|---|
| Rok vydání: | 2016 |
| Předmět: | |
| Zdroj: | Random Structures and Algorithms Volume 56 (4), 2020, pages 948-987 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1002/rsa.20906 |
| Popis: | 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. Comment: 46 pages, 3 figures; minor changes |
| Databáze: | arXiv |
| Externí odkaz: |
|