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 <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$b(G)\le \lceil n^\frac{1}{2}\rceil $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>b</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>≤</mo> <mrow> <mo>⌈</mo> <msup> <mi>n</mi> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> </msup> <mo>⌉</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$n_2$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>n</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation> degree-2 vertices, <Equation ID="Equ6"> <EquationSource Format="TEX">$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 .$</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <mi>b</mi> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> <mo>≤</mo> <mrow> <mo maxsize="2.047em" minsize="2.047em" stretchy="true">⌈</mo> </mrow> <msup> <mfenced close=")" open="("> <mi>n</mi> <mo>+</mo> <msub> <mi>n</mi> <mn>2</mn> </msub> <mo>-</mo> <mrow> <mo maxsize="1.623em" minsize="1.623em" stretchy="true">⌈</mo> </mrow> <msqrt> <mrow> <mi>n</mi> <mo>+</mo> <msub> <mi>n</mi> <mn>2</mn> </msub> <mo>+</mo> <mn>0.25</mn> </mrow> </msqrt> <mo>-</mo> <mn>1.5</mn> <mrow> <mo maxsize="1.623em" minsize="1.623em" stretchy="true">⌉</mo> </mrow> </mfenced> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> </msup> <mrow> <mo maxsize="2.047em" minsize="2.047em" stretchy="true">⌉</mo> </mrow> <mo>.</mo> </mrow> </math></EquationSource> </Equation>Hence, the conjecture holds for all trees of order n with at most <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\left\lfloor \sqrt{n-1}\right\rfloor $</EquationSource> <EquationSource Format="MATHML"><math> <mfenced close="⌋" open="⌊"> <msqrt> <mrow> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </msqrt> </mfenced> </math></EquationSource> </InlineEquation> degree-2 vertices.

The burning number conjecture holds for trees of order n with at most $\left\lfloor \sqrt{n-1}\right\rfloor $ degree-2 vertices

期刊论文
发表日期：

2026年3月2日

查看全文

Jiajun Ning,
Xian’an Jin,
Meiqiao Zhang

摘要

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)\le \lceil n^\frac{1}{2}\rceil $ $b (G) \leq ⌈ n^{\frac{1}{2}} ⌉$ 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 $n_2$ $n_{2}$ degree-2 vertices, $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 .$ $b (T) \leq ⌈ {(n + n_{2} - ⌈ \sqrt{n + n_{2} + 0.25} - 1.5 ⌉)}^{\frac{1}{2}} ⌉ .$ Hence, the conjecture holds for all trees of order n with at most $\left\lfloor \sqrt{n-1}\right\rfloor $ $⌊\sqrt{n - 1}⌋$ degree-2 vertices.

The burning number conjecture holds for trees of order n with at most \(\left\lfloor \sqrt{n-1}\right\rfloor \) degree-2 vertices

摘要