Počet záznamů: 1
Almost all trees are almost graceful
- 1.
SYSNO ASEP 0524449 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název Almost all trees are almost graceful Tvůrce(i) Adamaszek, A. (DK)
Allen, P. (GB)
Grosu, C. (CH)
Hladký, Jan (MU-W) RID, SAI, ORCIDZdroj.dok. Random Structures and Algorithms. - : Wiley - ISSN 1042-9832
Roč. 56, č. 4 (2020), s. 948-987Poč.str. 40 s. Jazyk dok. eng - angličtina Země vyd. US - Spojené státy americké Klíč. slova extremal graph theory ; graceful tree labelling ; tree Vědní obor RIV BA - Obecná matematika Obor OECD Pure mathematics Způsob publikování Omezený přístup Institucionální podpora MU-W - RVO:67985840 UT WOS 000514232400001 EID SCOPUS 85079856601 DOI 10.1002/rsa.20906 Anotace 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. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2021 Elektronická adresa https://doi.org/10.1002/rsa.20906
Počet záznamů: 1