Počet záznamů: 1
Almost all trees are almost graceful
- 1.0524449 - MÚ 2021 RIV US eng J - Článek v odborném periodiku
Adamaszek, A. - Allen, P. - Grosu, C. - Hladký, Jan
Almost all trees are almost graceful.
Random Structures and Algorithms. Roč. 56, č. 4 (2020), s. 948-987. ISSN 1042-9832. E-ISSN 1098-2418
GRANT EU: European Commission(XE) 628974 - PAECIDM
Institucionální podpora: RVO:67985840
Klíčová slova: extremal graph theory * graceful tree labelling * tree
Obor OECD: Pure mathematics
Impakt faktor: 1.131, rok: 2020
Způsob publikování: Omezený přístup
https://doi.org/10.1002/rsa.20906
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 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.
Trvalý link: http://hdl.handle.net/11104/0308811
Název souboru Staženo Velikost Komentář Verze Přístup Hladky.pdf 1 992.7 KB Vydavatelský postprint vyžádat
Počet záznamů: 1