Ta Sheng Tan ; Wen Chean Teh - A Note on Graph Burning of Path Forests

dmtcs:12709 - Discrete Mathematics & Theoretical Computer Science, August 21, 2024, vol. 26:3 - https://doi.org/10.46298/dmtcs.12709
A Note on Graph Burning of Path ForestsArticle

Authors: Ta Sheng Tan ; Wen Chean Teh

    Graph burning is a natural discrete graph algorithm inspired by the spread of social contagion. Despite its simplicity, some open problems remain steadfastly unsolved, notably the burning number conjecture, which says that every connected graph of order $m^2$ has burning number at most $m$. Earlier, we showed that the conjecture also holds for a path forest, which is disconnected, provided each of its paths is sufficiently long. However, finding the least sufficient length for this to hold turns out to be nontrivial. In this note, we present our initial findings and conjectures that associate the problem to some naturally impossibly burnable path forests. It is noteworthy that our problem can be reformulated as a topic concerning sumset partition of integers.


    Volume: vol. 26:3
    Section: Discrete Algorithms
    Published on: August 21, 2024
    Accepted on: July 12, 2024
    Submitted on: December 19, 2023
    Keywords: Mathematics - Combinatorics,05C85, 05A17, 68R10

    Consultation statistics

    This page has been seen 388 times.
    This article's PDF has been downloaded 193 times.