Graphs with burning number three

Yinkui Li, Guiyu Shi and Xiaoxiao Qin

Applied Mathematics and Computation, 2025, vol. 487, issue C

Abstract: Recently, Bonato et al. proposed the concept of the burning number of a graph to measure the speed of contagion spread on a network. They pointed out that the burning number of graph G is b(G)≥2 and showed that the graph G with burning number 2 if and only if G has maximum degree |V(G)|−1 or |V(G)|−2. Consider the problem of finding the maximum degree of a graph is solvable in polynomial time, graphs with burning number 2 can be recognized in polynomial time and thus the lower bound of burning number be improved to 3. In this paper, we characterize graphs with burning number 3 in terms of maximum degree and diameter.

Keywords: Burning number; Tree; Diameter (search for similar items in EconPapers)
Date: 2025
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300324005617
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:487:y:2025:i:c:s0096300324005617

DOI: 10.1016/j.amc.2024.129100

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().