Skip to content
DraconiticResearch
Search Sources API
182,460 studies31 sourcesUpdated 36 min ago
PreprintCC BY 4.0arXiv

A Structural Approach to Burning Number

  • Jean Guillaume
  • Tyriana Williams
Open at sourcePDFDOICite

Abstract

Graph burning is a deterministic discrete-time process that models the propagation of information within a network as a set of fires that spread in a graph. The associated graph parameter, the burning number, measures the speed of that spread. The smaller the burning number of a graph is, the faster information spreads in the corresponding network. In this paper, we mainly study the burning number from a structural point of view. In particular, we structurally characterize all graphs with burning number 2. We then proceed to compute the burning number of split graphs and { K2+2K1, P4, C4}-free graphs. In particular, we show that connected split graphs and connected { K2+2K1, P4, C4}-free graphs are well-burnable. Lastly, we provide a blueprint on how to investigate the burning number of a given social network.

Related

  1. On the Burning Game: Nordhaus-Gaddum Bounds and Graph Products
    Nina Chiarelli, Vesna Iršič Chenoweth, Marko Jakovac +2
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Burning Signed Graphs
    Shaun Fallat, Himanshu Gupta, Kamyar Khodamoradi +1
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Inertial multiplicity bounds for two dimensional projective representations and bounds for the number of PSL2(𝔽q) and PGL2(𝔽q) number fields
    Brandon Alberts
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv
  4. Tree-independence number VIII. 3PC-free graphs have logarithmic tree-independence number
    Maria Chudnovsky, Julien Codsi, Ajaykrishnan E S +2
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. Unknotting number is not additive under connected sum
    Mark Brittenham, Susan Hermiller
    Annals of MathematicsPeer-reviewedLicence not statedFull text5 citedGeometry & topologyOpenAlex

Cite

BibTeXRIS
BibTeX
@misc{guillaume2026structural,
  title = {{A Structural Approach to Burning Number}},
  author = {Jean Guillaume and Tyriana Williams},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2606.04178},
  eprint = {2606.04178},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2606.04178},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - A Structural Approach to Burning Number
AU  - Jean Guillaume
AU  - Tyriana Williams
PY  - 2026
DA  - 2026/10/01
PB  - arXiv
DO  - 10.48550/arxiv.2606.04178
UR  - https://arxiv.org/abs/2606.04178
AB  - Graph burning is a deterministic discrete-time process that models the propagation of information within a network as a set of fires that spread in a graph. The associated graph parameter, the burning number, measures the speed of that spread. The smaller the burning number of a graph is, the faster information spreads in the corresponding network. In this paper, we mainly study the burning number from a structural point of view. In particular, we structurally characterize all graphs with burning number 2. We then proceed to compute the burning number of split graphs and { K_2+2K_1, P_4, C_4}-free graphs. In particular, we show that connected split graphs and connected { K_2+2K_1, P_4, C_4}-free graphs are well-burnable. Lastly, we provide a blueprint on how to investigate the burning number of a given social network.
ER  -