Propagation processes on (hyper)graphs: where zero forcing and burning meet

The burning and forcing processes are both instances of propagation processes on graphs that are commonly used to model real-world spreading phenomena. The contribution of this paper is two-fold. We first establish a connection between these two propagation processes via hypergraphs. We do so by showing a sharp upper bound on the zero forcing number of the incidence graph of a hypergraph in terms of the lazy burning number of the hypergraph, which builds up on and improves a result by Bonato, Jones, Marbach, Mishura and Zhang (Theor. Comput. Sci., 2025). Secondly, we deepen the understanding of the role of the burning process in the context of graph spectral characterizations, whose goal is to understand which graph properties are encoded in the spectrum. While for several graph properties, including the zero forcing number, it is known that the spectrum does not encode them, this question remained open for the burning number. We solve this problem by constructing infinitely many pairs of cospectral graphs which have a different burning number.

• Publication year

  2026

• Venue

  Unknown venue

• Publication date

  2026-02-13

• Fields of study

  Mathematics

• Identifiers
  arXiv 2602.13149
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Burning numbers via eigenpolytopes -- Hamming graphs, Johnson graphs, and halved cubes

  2025cited by this paper
• Extending graph burning to hypergraphs

  2024cited by this paper
• Hypergraph burning, matchings, and zero forcing

  2024cited by this paper
• Constructions of cospectral graphs with different zero forcing numbers

  2021cited by this paper
• A survey of graph burning

  2020cited by this paper
• Generalized cospectral graphs with and without Hamiltonian cycles

  2020cited by this paper
• Burning a graph is hard

  2015cited by this paper
• Upper bounds on the k-forcing number of a graph

  2014cited by this paper
• Cospectral regular graphs with and without a perfect matching

  2014cited by this paper
• Burning a Graph as a Model of Social Contagion

  2014cited by this paper
• Spectra of Graphs

  2011cited by this paper
• Synchronization in complex networks

  2008cited by this paper
• Distance regularity and the spectrum of graphs

  1996cited by this paper
• Transmitting in the n-Dimensional Cube

  1992cited by this paper
• Bootstrap percolation on a Bethe lattice

  1979cited by this paper
• Threshold Models of Collective Behavior

  1978cited by this paper

• No citing papers are available for this paper.