The burning number conjecture holds for trees of order n with at most $$\left\lfloor \sqrt{n-1}\right\rfloor $$ degree-2 vertices
Graphs and Combinatorics · 2026-04 · 42 (2)
DOI: 10.1007/s00373-026-03024-w ↗Kurz gefasst
Fachartikel in der Zeitschrift Graphs and Combinatorics, online erschienen am 02.03.2026. Verfasst von Jiajun Ning und 2 weiteren Autor:innen. Die Arbeit nennt 8 Literaturangaben. Gefördert von: National Natural Science Foundation of China, Natural Science Foundation of Xiamen, China, Foundation for Cultivated Young Talents of Fujian Province, China.
Abstract (Originalsprache)
Inspired by the spread of information in social networks and graph-theoretic processes such as Firefighting and graph cleaning, Bonato, Janssen and Roshanbin introduced in 2016 the burning number b(G) of any finite graph G. They conjectured that b(G)≤⌈n12⌉\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$b(G)\le \lceil n^\frac{1}{2}\rceil $$\end{document} holds for all connected graphs G of order n, and observed that it suffices to prove the conjecture for all trees. In 2024, Murakami confirmed the conjecture for trees without degree-2 vertices. In this paper, we prove that for all trees T of order n with n2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n_2$$\end{document} degree-2 vertices, b(T)≤⌈n+n2-⌈n+n2+0.25-1.5⌉12⌉.\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$b(T)\le \bigg \lceil \left( n+n_2-\Big \lceil \sqrt{n+n_2+0.25}-1.5\Big \rceil \right) ^{\frac{1}{2}}\bigg \rceil .$$\end{document}Hence, the conjecture holds for all trees of order n with at most n-1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\left\lfloor \sqrt{n-1}\right\rfloor $$\end{document} degree-2 vertices.
Förderung
- National Natural Science Foundation of China
- Natural Science Foundation of Xiamen, China
- Foundation for Cultivated Young Talents of Fujian Province, China
Zitieren
APA
Ning, J., Jin, X., & Zhang, M. (2026). The burning number conjecture holds for trees of order n with at most $$\left\lfloor \sqrt{n-1}\right\rfloor $$ degree-2 vertices. Graphs and Combinatorics, 42(2). https://doi.org/10.1007/s00373-026-03024-w
Vancouver
Ning J, Jin X, Zhang M. The burning number conjecture holds for trees of order n with at most $$\left\lfloor \sqrt{n-1}\right\rfloor $$ degree-2 vertices. Graphs and Combinatorics. 2026;42(2). doi:10.1007/s00373-026-03024-w
BibTeX
@article{Ning2026,
author = {Ning, Jiajun and Jin, Xian’an and Zhang, Meiqiao},
title = {The burning number conjecture holds for trees of order n with at most $$\left\lfloor \sqrtn-1\right\rfloor $$ degree-2 vertices},
journal = {Graphs and Combinatorics},
year = {2026},
volume = {42},
number = {2},
doi = {10.1007/s00373-026-03024-w}
}
EUVIMED