Burnability of double spiders and path forests

Ta Sheng Tan and Wen Chean Teh

Applied Mathematics and Computation, 2023, vol. 438, issue C

Abstract: The burning number of a graph can be used to measure the spreading speed of contagion in a network. The burning number conjecture is arguably the main unresolved conjecture related to this graph parameter, which can be settled by showing that every tree of order m2 has burning number at most m. This is known to hold for many classes of trees, including spiders - trees with exactly one vertex of degree greater than two. In fact, it has been verified that certain spiders of order slightly larger than m2 also have burning numbers at most m, a result that has then been conjectured to be true for all trees. The first focus of this paper is to verify this slightly stronger conjecture for double spiders - trees with two vertices of degrees at least three and they are adjacent. Our other focus concerns the burning numbers of path forests, a class of graphs in which their burning numbers are naturally related to that of spiders and double spiders. Here, our main result shows that a path forest of order m2 with a sufficiently long shortest path has burning number exactly m, the smallest possible for any path forest of the same order.

Keywords: Spread of social contagion; Burning number conjecture; Graph algorithm; Double spider; Path forest (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300322006488
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:438:y:2023:i:c:s0096300322006488

DOI: 10.1016/j.amc.2022.127574

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