Graph burning: Tight bounds on the burning numbers of path forests and spiders

Ta Sheng Tan and Wen Chean Teh

Applied Mathematics and Computation, 2020, vol. 385, issue C

Abstract: In 2016, Bonato, Janssen, and Roshanbin introduced graph burning as a discrete process that models the spread of social contagion. Although the burning process is a simple algorithm, the problem of determining the least number of rounds needed to completely burn a graph, called the burning number of the graph, is NP-complete even for elementary graph structures like spiders. An early conjecture that every connected graph of order m2 can be burned in at most m rounds is the main motivator of this study. Attempts to prove the conjecture have resulted in various upper bounds for the burning number and validation of the conjecture for certain elementary classes of graphs. In this work, we find a tight upper bound for the order of a spider for it to be burned within a given number of rounds. Our result shows that the tight bound depends on the structure of the spider under consideration, namely the number of arms. This strengthens the previously known results on spiders in relation to the conjecture. More importantly, this opens up potential enquiry into the connection between burning numbers and certain characteristics of graphs. Finally, a tight upper bound for the order of a path forest for it to be burned within a given number of rounds is obtained, thus completing previously known partial corresponding results.

Keywords: Burning number conjecture; Graph algorithm; Spider; Path forest (search for similar items in EconPapers)
Date: 2020
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300320304082
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:385:y:2020:i:c:s0096300320304082

DOI: 10.1016/j.amc.2020.125447

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 ().