{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T15:13:29Z","timestamp":1774624409556,"version":"3.50.1"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2024,6,25]],"date-time":"2024-06-25T00:00:00Z","timestamp":1719273600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,6,25]],"date-time":"2024-06-25T00:00:00Z","timestamp":1719273600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2024,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Graph burning is a discrete time process which can be used to model the spread of social contagion. One is initially given a graph of unburned vertices. At each round (time step), one vertex is burned; unburned vertices with at least one burned neighbour from the previous round also becomes burned. The burning number of a graph is the fewest number of rounds required to burn the graph. It has been conjectured that for a graph on\u00a0<jats:italic>n<\/jats:italic> vertices, the burning number is at most\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\lceil \\sqrt{n}\\rceil $$<\/jats:tex-math><mml:math xmlns:mml=\"https:\/\/2.zoppoz.workers.dev:443\/http\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>\u2308<\/mml:mo>\n                    <mml:msqrt>\n                      <mml:mi>n<\/mml:mi>\n                    <\/mml:msqrt>\n                    <mml:mo>\u2309<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We show that the graph burning conjecture is true for trees without degree-2 vertices.<\/jats:p>","DOI":"10.1007\/s00373-024-02812-6","type":"journal-article","created":{"date-parts":[[2024,6,25]],"date-time":"2024-06-25T02:01:26Z","timestamp":1719280886000},"update-policy":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["The Burning Number Conjecture is True for Trees without Degree-2 Vertices"],"prefix":"10.1007","volume":"40","author":[{"ORCID":"https:\/\/2.zoppoz.workers.dev:443\/https\/orcid.org\/0000-0003-1355-5884","authenticated-orcid":false,"given":"Yukihiro","family":"Murakami","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,6,25]]},"reference":[{"issue":"2","key":"2812_CR1","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1002\/jgt.3190140212","volume":"14","author":"MO Albertson","year":"1990","unstructured":"Albertson, M.O., Berman, D.M., Hutchinson, J.P., Thomassen, C.: Graphs with homeomorphically irreducible spanning trees. J. Graph Theory 14(2), 247\u2013258 (1990)","journal-title":"J. Graph Theory"},{"key":"2812_CR2","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/0166-218X(92)90121-P","volume":"37","author":"N Alon","year":"1992","unstructured":"Alon, N.: Transmitting in the $$n$$-dimensional cube. Discret. Appl. Math. 37, 9\u201311 (1992)","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"2812_CR3","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1007\/s11856-023-2499-3","volume":"256","author":"N Alon","year":"2023","unstructured":"Alon, N.: Spanning trees with few non-leaves. Israel J. Math. 256(1), 9\u201320 (2023)","journal-title":"Israel J. Math."},{"key":"2812_CR4","unstructured":"Bastide, P., Bonamy, M., Bonato, A., Charbit, P., Kamali, S., Pierron, T., Rabie, M.: Improved pyrotechnics: closer to the burning graph conjecture. arXiv preprint arXiv:2110.10530 (2021)"},{"key":"2812_CR5","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/j.dam.2017.07.016","volume":"232","author":"S Bessy","year":"2017","unstructured":"Bessy, S., Bonato, A., Janssen, J., Rautenbach, D., Roshanbin, E.: Burning a graph is hard. Discret. Appl. Math. 232, 73\u201387 (2017)","journal-title":"Discret. Appl. Math."},{"key":"2812_CR6","doi-asserted-by":"crossref","unstructured":"Bonato, A., Janssen, J., Roshanbin, E.: Burning a graph as a model of social contagion. In: Algorithms and Models for the Web Graph: 11th International Workshop, WAW 2014, Beijing, China, December 17-18, 2014, Proceedings 11, pp. 13\u201322. Springer (2014)","DOI":"10.1007\/978-3-319-13123-8_2"},{"key":"2812_CR7","unstructured":"Bonato, A.: A survey of graph burning. arXiv preprint arXiv:2009.10642 (2020)"},{"key":"2812_CR8","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/j.tcs.2018.05.035","volume":"794","author":"A Bonato","year":"2019","unstructured":"Bonato, A., Lidbetter, T.: Bounds on the burning numbers of spiders and path-forests. Theoret. Comput. Sci. 794, 12\u201319 (2019)","journal-title":"Theoret. Comput. Sci."},{"issue":"1\u20132","key":"2812_CR9","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1080\/15427951.2015.1103339","volume":"12","author":"A Bonato","year":"2016","unstructured":"Bonato, A., Janssen, J., Roshanbin, E.: How to burn a graph. Internet Math. 12(1\u20132), 85\u2013100 (2016)","journal-title":"Internet Math."},{"issue":"1\u20132","key":"2812_CR10","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1017\/S0963548311000526","volume":"21","author":"G Chen","year":"2012","unstructured":"Chen, G., Ren, H., Shan, S.: Homeomorphically irreducible spanning trees in locally connected graphs. Comb. Probab. Comput. 21(1\u20132), 107\u2013111 (2012)","journal-title":"Comb. Probab. Comput."},{"key":"2812_CR11","unstructured":"Das, S., Islam, S.S., Mitra, R.M., Paul, S.: Burning a binary tree and its generalization. arXiv preprint arXiv:2308.02825 (2023)"},{"issue":"4","key":"2812_CR12","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1002\/jgt.1013","volume":"37","author":"G Ding","year":"2001","unstructured":"Ding, G., Johnson, T., Seymour, P.: Spanning trees with many leaves. J. Graph Theory 37(4), 189\u2013197 (2001)","journal-title":"J. Graph Theory"},{"key":"2812_CR13","unstructured":"Furuya, M., Tsuchiya, S.: New strategy on the existence of a spanning tree without small degree stems. arXiv preprint arXiv:2303.03762 (2023)"},{"key":"2812_CR14","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/BF02559543","volume":"101","author":"F Harary","year":"1959","unstructured":"Harary, F., Prins, G.: The number of homeomorphically irreducible trees, and other species. Acta Math. 101, 141\u2013162 (1959)","journal-title":"Acta Math."},{"key":"2812_CR15","doi-asserted-by":"crossref","unstructured":"Hiller, M., Koster, A.M., Triesch, E.: On the burning number of $$p$$-caterpillars. In: Graphs and Combinatorial Optimization: From Theory to Applications: CTW2020 Proceedings, pp. 145\u2013156. Springer (2020)","DOI":"10.1007\/978-3-030-63072-0_12"},{"key":"2812_CR16","unstructured":"Janssen, R.: The burning number of directed graphs: bounds and computational complexity. arXiv preprint arXiv:2001.03381 (2020)"},{"key":"2812_CR17","unstructured":"Lemke, P.: The maximum leaf spanning tree problem for cubic graphs is NP-complete. IMA Preprint Series 428 (1988)"},{"key":"2812_CR18","unstructured":"Martinsson, A.: On the approximability of the burning number. arXiv preprint arXiv:2308.04390 (2023)"},{"key":"2812_CR19","unstructured":"Norin, S., Turcotte, J.: The burning number conjecture holds asymptotically. arXiv preprint arXiv:2207.04035 (2022)"},{"issue":"10","key":"2812_CR20","doi-asserted-by":"publisher","first-page":"2893","DOI":"10.1016\/j.disc.2019.01.032","volume":"342","author":"S Zhai","year":"2019","unstructured":"Zhai, S., Wei, E., He, J., Ye, D.: Homeomorphically irreducible spanning trees in hexangulations of surfaces. Discret. Math. 342(10), 2893\u20132899 (2019)","journal-title":"Discret. Math."}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/link.springer.com\/content\/pdf\/10.1007\/s00373-024-02812-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/link.springer.com\/article\/10.1007\/s00373-024-02812-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/link.springer.com\/content\/pdf\/10.1007\/s00373-024-02812-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,9]],"date-time":"2024-08-09T19:04:33Z","timestamp":1723230273000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/link.springer.com\/10.1007\/s00373-024-02812-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,25]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,8]]}},"alternative-id":["2812"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1007\/s00373-024-02812-6","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"value":"0911-0119","type":"print"},{"value":"1435-5914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6,25]]},"assertion":[{"value":"2 January 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 June 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 June 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 June 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The author declares that they have no Conflict of interest. The author has no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"82"}}