Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 4 min ago
PreprintarXiv licencearXiv

On the Burning Game: Nordhaus-Gaddum Bounds and Graph Products

  • Nina Chiarelli
  • Vesna Iršič Chenoweth
  • Marko Jakovac
  • William B. Kinnersley
  • Mirjana Mikalački
Open at sourcePDFDOICite

Abstract

We continue research on the burning game on graphs. Given a graph G, two players, Burner and Staller, take turns in selecting vertices of G to burn. All burned vertices spread fire to unburned neighboring vertices, as in the burning process. The goal of Burner is to burn the graph as quickly as possible, while Staller wants the process to last as long as possible. If both players play optimally, then the number of time steps needed to burn the whole graph G is the game burning number bg(G) if Burner makes the first move, and the Staller-start game burning number bg'(G) if Staller starts. In this paper, we study this game further, establishing Nordhaus-Gaddum bounds on the game burning number, as well as bounds for four different types of graph products: strong, Cartesian, lexicographic and corona products.

Related

  1. Generalized Nordhaus--Gaddum Inequalities for Eigenvalues
    Sahil Agarwal, Carter Antley, Joseph Aulenbacher +6
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Selfless reduced free products and graph products of C⁎-algebras
    Felipe Flores, Mario Klisse, Mícheál Ó Cobhthaigh +1
    Advances in MathematicsPeer-reviewedCC BY14 citedMathematical physicsOpenAlex
  3. Rotation groups, mediangle graphs, and periagroups: A unified point of view on Coxeter groups and graph products of groups
    Anthony Genevois
    Groups Geometry and DynamicsPeer-reviewedCC BY13 citedGeometry & topologyOpenAlex
  4. Combination Theorems and the Farrell--Jones Conjecture for Graph Products of Pairs
    I. Gkeneralis, S. Prassidis
    arXivPreprintCC BY 4.0Full textGeometry & topologyarXiv
  5. Lower bounds in H2-rational approximation to Blaschke products
    Laurent Baratchart, Alexander Borichev, Sylvain Chevillard +2
    Research in the Mathematical SciencesPeer-reviewedCC BY 4.0Full textAnalysis & PDEsHAL

Cite

BibTeXRIS
BibTeX
@misc{chiarelli2026burning,
  title = {{On the Burning Game: Nordhaus-Gaddum Bounds and Graph Products}},
  author = {Nina Chiarelli and Vesna Iršič Chenoweth and Marko Jakovac and William B. Kinnersley and Mirjana Mikalački},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.38255},
  eprint = {2609.38255},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.38255},
}
RIS
TY  - UNPB
TI  - On the Burning Game: Nordhaus-Gaddum Bounds and Graph Products
AU  - Nina Chiarelli
AU  - Vesna Iršič Chenoweth
AU  - Marko Jakovac
AU  - William B. Kinnersley
AU  - Mirjana Mikalački
PY  - 2026
DA  - 2026/09/29
PB  - arXiv
DO  - 10.48550/arxiv.2609.38255
UR  - https://arxiv.org/abs/2609.38255
AB  - We continue research on the burning game on graphs. Given a graph G, two players, Burner and Staller, take turns in selecting vertices of G to burn. All burned vertices spread fire to unburned neighboring vertices, as in the burning process. The goal of Burner is to burn the graph as quickly as possible, while Staller wants the process to last as long as possible. If both players play optimally, then the number of time steps needed to burn the whole graph G is the game burning number b_g(G) if Burner makes the first move, and the Staller-start game burning number b_g'(G) if Staller starts. In this paper, we study this game further, establishing Nordhaus-Gaddum bounds on the game burning number, as well as bounds for four different types of graph products: strong, Cartesian, lexicographic and corona products.
ER  -