{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,7]],"date-time":"2023-09-07T20:34:07Z","timestamp":1694118847914},"reference-count":24,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2020,2,19]],"date-time":"2020-02-19T00:00:00Z","timestamp":1582070400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"name":"Humboldt Foundation (A.A.) Deutsche Forschungsgemeinschaft (C.G.) People Programme (Marie Curie Actions) of the European Union's Seventh Framework Programme","award":["628974 (J.H.)"],"award-info":[{"award-number":["628974 (J.H.)"]}]},{"name":"The Institute of Mathematics","award":["RVO:67985840"],"award-info":[{"award-number":["RVO:67985840"]}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Random Struct Algorithms"],"published-print":{"date-parts":[[2020,7]]},"abstract":"<jats:p>The Graceful Tree Conjecture of Rosa from 1967 asserts that the vertices of each tree <jats:italic>T<\/jats:italic> of order <jats:italic>n<\/jats:italic> can be injectively labeled by using the numbers {1,2,\u2026,<jats:italic>n<\/jats:italic>} 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 <jats:italic>\u03b3<\/jats:italic>&gt;0 and for all <jats:italic>n<\/jats:italic>&gt;<jats:italic>n<\/jats:italic><jats:sub>0<\/jats:sub>(<jats:italic>\u03b3<\/jats:italic>). Suppose that (i) the maximum degree of <jats:italic>T<\/jats:italic> is bounded by <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/rsa20906-math-0001.png\" xlink:title=\"urn:x-wiley:rsa:media:rsa20906:rsa20906-math-0001\" \/>), and (ii) the vertex labels are chosen from the set {1,2,\u2026,\u2308(1+<jats:italic>\u03b3<\/jats:italic>)<jats:italic>n<\/jats:italic>\u2309}. Then there is an injective labeling of <jats:italic>V<\/jats:italic>(<jats:italic>T<\/jats:italic>) such that the absolute differences on the edges are pairwise distinct. In particular, asymptotically almost all trees on <jats:italic>n<\/jats:italic> vertices admit such a labeling. The proof proceeds by showing that a certain very natural randomized algorithm produces a desired labeling with high probability.<\/jats:p>","DOI":"10.1002\/rsa.20906","type":"journal-article","created":{"date-parts":[[2020,2,19]],"date-time":"2020-02-19T13:50:07Z","timestamp":1582120207000},"page":"948-987","update-policy":"http:\/\/dx.doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Almost all trees are almost graceful"],"prefix":"10.1002","volume":"56","author":[{"given":"Anna","family":"Adamaszek","sequence":"first","affiliation":[{"name":"SimCorp Copenhagen Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Allen","sequence":"additional","affiliation":[{"name":"Department of Mathematics London School of Economics London United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Codru\u0163","family":"Grosu","sequence":"additional","affiliation":[{"name":"Google Zurich Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jan","family":"Hladk\u00fd","sequence":"additional","affiliation":[{"name":"Institute of Mathematics of the Czech Academy of Sciences Praha Czech Republic"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2020,2,19]]},"reference":[{"key":"e_1_2_7_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2019.106739"},{"key":"e_1_2_7_3_1","first-page":"18","volume-title":"Graph Theory and Combinatorics","author":"Bermond J.C.","year":"1979"},{"key":"e_1_2_7_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-015-1277-2"},{"key":"e_1_2_7_5_1","doi-asserted-by":"publisher","DOI":"10.37236\/1621"},{"key":"e_1_2_7_6_1","first-page":"337","article-title":"Operations of interlaced trees and graceful trees","volume":"21","author":"Chen W.C.","year":"1997","journal-title":"Southeast Asian Bull. Math."},{"key":"e_1_2_7_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-017-1504-0"},{"key":"e_1_2_7_8_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms.12179"},{"key":"e_1_2_7_9_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1749-6632.1979.tb32792.x"},{"key":"e_1_2_7_10_1","first-page":"384","article-title":"A dynamic survey of graph labeling","author":"Gallian J.A.","year":"2014","journal-title":"Electron. J. Combin."},{"key":"e_1_2_7_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-1-4832-3187-7.50008-8"},{"key":"e_1_2_7_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/0601045"},{"key":"e_1_2_7_13_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_2_7_14_1","doi-asserted-by":"crossref","DOI":"10.1002\/9781118032718.scard","volume-title":"Wiley\u2010Interscience Series in Discrete Mathematics and Optimization","author":"Janson S.","year":"2000"},{"key":"e_1_2_7_15_1","doi-asserted-by":"publisher","DOI":"10.4171\/JEMS\/909"},{"key":"e_1_2_7_16_1","doi-asserted-by":"publisher","DOI":"10.1090\/tran\/7411"},{"key":"e_1_2_7_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2016.03.003"},{"key":"e_1_2_7_18_1","article-title":"Embedding rainbow trees with applications to graph labelling and decomposition","author":"Montgomery R.","journal-title":"J. EMS"},{"key":"e_1_2_7_19_1","doi-asserted-by":"publisher","DOI":"10.1307\/mmj\/1029000098"},{"key":"e_1_2_7_20_1","first-page":"218","volume-title":"Numerotation gracieuse des oliviers","author":"Pastel A.M.","year":"1978"},{"key":"e_1_2_7_21_1","first-page":"162","volume-title":"Theory of Graphs and its Applications (Proc. Sympos. Smolenice 1963)","author":"Ringel G.","year":"1964"},{"key":"e_1_2_7_22_1","first-page":"349","volume-title":"Theory of Graphs (Internat. Symposium, Rome, July 1966)","author":"Rosa A.","year":"1967"},{"key":"e_1_2_7_23_1","first-page":"53","article-title":"All banana trees are graceful","volume":"4","author":"Sethuraman G.","year":"2009","journal-title":"Adv. Appl. Disc. Math."},{"key":"e_1_2_7_24_1","doi-asserted-by":"publisher","DOI":"10.2298\/AADM141009017W"},{"key":"e_1_2_7_25_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177004612"}],"container-title":["Random Structures &amp; Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.20906","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.20906","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full-xml\/10.1002\/rsa.20906","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.20906","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,6]],"date-time":"2023-09-06T02:40:41Z","timestamp":1693968041000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.20906"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,19]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,7]]}},"alternative-id":["10.1002\/rsa.20906"],"URL":"https:\/\/doi.org\/10.1002\/rsa.20906","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"value":"1042-9832","type":"print"},{"value":"1098-2418","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,2,19]]},"assertion":[{"value":"2016-08-04","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-09-04","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-02-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}