Propagation processes on (hyper)graphs: where zero forcing and burning meet Aida Abiad, Pax Mallee Abstract 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. 1 Introduction The burning and forcing processes often appear across mathematics and computer science, but also in other fields such as statistical mechanics [ 16 ] , physics [ 5 ] or social network analysis [ 13 ] ), among others. In such fields, burning and zero forcing are used to model technical or societal processes. For an overview of the different models and applications, refer to the survey [ 10 ] and the book [ 15 ] . The concept of graph burning, which was introduced in [ 8 ] , is a deterministic, discrete-time model for the spread of social contagion on a graph. A social network can be modeled by a graph in which the vertices represent people and the edges represent relationships. For example, on a graph whose vertices correspond to Facebook users, edges may represent users who are Facebook friends. Information, such as gossip, rumors, or memes, can spread from vertex to vertex over time along edges of the graph and we model the process using discrete time-steps called rounds. Such information may not stem from a single source vertex; there may be a number of sources that appear over time in the graph. Authors often refer to vertices as unburned (unaware of the information) and burned (aware of the information) since rumors can appear to spread swiftly like fire. We will instead use colors to depict these states: uncolored for unburned and red for burned. Although computing the burning number is NP-complete (it is so even when restricted to trees of maximum degree three; see [ 6 , Theorem 6] ), several authors have established the burning number for several graph classes, see e.g. [ 3 , 17 ] . Hypergraph burning was introduced in [ 11 ] as a natural extension of graph burning. The rules for hypergraph burning are identical to those for burning graphs, except for how burning propagates within a hyperedge. Recall that in a hypergraph, a singleton edge contains exactly one vertex. In hypergraphs, the burning spreads to a vertex v in round r if and only if there is a non-singleton hyperedge \{v,u_{1},\dots,u_{k}\} such that v was not burned and each of u_{1},u_{2},\dots,u_{k} was burned at the end of round r-1 . In particular, a vertex becomes burned if it is the only unburned vertex in a hyperedge. A natural variation of burning that is our principal focus here is lazy hypergraph burning , where a set of vertices is chosen to burn in the first round only; no other vertices are chosen to burn in later rounds. The lazy burning number of H , denoted b_{L}(H) and introduced in [ 9 ] , is the minimum cardinality of a set of vertices burned in the first round that eventually burns all vertices. The lazy burning was introduced in order to establish a link with another well-known graph process: zero forcing. Zero forcing is a graph coloring process used to model spreading phenomena in real-world scenarios. It can also be viewed as a single-player combinatorial game on a graph, where the player’s goal is to select a subset of vertices of minimum cardinality that eventually leads to all vertices of the graph being colored. In lazy burning, only one set of vertices is chosen to burn in the first round. In hypergraphs, burned vertices spread when all but one vertex in a hyperedge is burned. The lazy burning number is the minimum number of initially burned vertices that eventually burn all vertices. Recently, the authors of [ 9 ] showed a characterization of lazy burning sets in hypergraphs via zero forcing sets in their incidence graphs. This was then used to derive a lower bound on the lazy burning of a hypergraph in terms of the zero forcing number of its incidence graph, see [ 9 , Theorem 25] and the text after. However, the tightness of this bound was not discussed. Motivated by understanding the tightness of the bound derived from [ 9 , Theorem 25] , and with the aim of further understanding the connection between the burning process and the zero forcing process, in this paper we derive an improved tight upper bound on the zero forcing number of the incidence graph of a hypergraph in terms of the lazy burning number of the hypergraph (see Theorem 3 ). We also provide some hypergraph classes that meet the new bound with equality (see Proposition 3.5 ). In the second part of this paper we focus on the problem of graph spectral characterization in connection with the burning number. Spectral graph characterizations seek to study relations between the spectrum of a graph and its combinatorial properties by investigating the spectrum of the associated matrix. Some properties of a graph are known to be characterized by the spectrum of the associated matrix [ 2 ] . However, not all graph properties can be characterized by the graph spectrum. If that is not the case, then there exists a pair of non-isomorphic graphs with the same spectrum ( cospectral graphs ) that do not share that same property, instances of such graph properties were investigated, among others, in [ 14 , 12 , 7 ] . Recently, also the zero forcing number has been shown not to be characterized by the spectrum [ 1 ] . In the second part of this paper we continue this line of research by showing that the burning number of a graph does not follow from the spectrum of the graph adjacency matrix (see Corollary 4.6 ), showing yet another analogy between both graph processes. We do so by providing a construction of two nonsiomorphic graph classes that are cospectral but have different burning numbers. 2 Preliminaries Throughout this paper, we consider G=(V(G),E(G)) to be an undirected simple graph of order |V|=n . The adjacency matrix of a graph G=(V(G),E(G)) is the n\times n -matrix A where the i,j entry A_{ij} is 1 if \{v_{i},v_{j}\}\in E(G) and 0 otherwise. The spectrum of a graph is the set of its adjacency eigenvalues. A hypergraph H consists of a non-empty vertex set V(H) vertices and a collection E(H) of subsets of V(H) whose elements are called hyperedges . An edge that contains exactly one vertex is called a singleton hyperedge. \displaystyle v_{3} \displaystyle v_{4} \displaystyle v_{1} \displaystyle v_{2} \displaystyle h_{1} \displaystyle h_{2} \displaystyle h_{3} Figure 1 : A hypergraph with 4 vertices and 3 hyperedges. For a hypergraph, one can define a graph that describes the incidence relationship between the vertices of the hypergraph and its hyperedges. The incidence graph of a hypergraph H , denoted IG(H) , is a bipartite graph with vertex set V(H)\cup E(H) and edge set \{vh\mid v\in V(H),h\in E(H)\text{ such that }v\in h\} . \displaystyle v_{1} \displaystyle v_{2} \displaystyle v_{3} \displaystyle v_{4} \displaystyle h_{1} \displaystyle h_{2} \displaystyle h_{3} Figure 2 : The incidence graph of the hypergraph in Figure 1 . 2.1 The zero forcing process on graphs The zero forcing process on a graph G is defined as follows. Initially, there is a subset B of blue vertices, while all other vertices are white. The color change rule dictates that at each step, a blue vertex with exactly one white neighbor will force its white neighbor to become blue. Each vertex will remain the same color from the previous step unless affected by the color change rule. The set B is said to be a zero forcing set if, by iteratively applying the color change rule, all of V becomes blue. The zero forcing number of G is the minimum cardinality of a zero forcing set in G , denoted by Z(G) . The following result will be used in Section 3 . Theorem 2.1 . (cf. [ 15 ] ) If G is a disconnected graph with connected components \{G_{i}\}_{1\leq i\leq k} , then Z(G)=\sum_{i=1}^{k}Z(G_{i}). An interesting observation can be made on the vertices in a minimal zero forcing set. At least one neighbor of every vertex in the zero forcing set must initially be uncolored. This observation was generalized for the k -forcing process in [ 4 ] . However, in this paper only the zero forcing process for k=1 will be used. Lemma 2.2 . [ 4 ] Let G be a graph of order n\geq 2 with a minimum degree \delta\geq 1 . Let B be a minimum zero forcing set of G . Then for each v\in V(G) , there is at least one vertex w\in V(G)\backslash B that is adjacent to v . 2.2 The burning process on (hyper)graphs Consider a graph G=(V(G),E(G)) . The vertices of the graph G can be either burned or unburned throughout the process. Initially, in the first round t=0 , all vertices are unburned. In each round t\geq 1 , an unburned vertex is chosen to become burned, if there is one, and is called a source . An unburned vertex remains unburned unless it becomes burned by the burning process, and once a vertex becomes burned, it remains burned for the rest of the process. If a vertex is burned in round t , then all its neighbors become burned in round t+1 . The process ends when all vertices are burned. The sources that are chosen over time form a burning sequence , and the shortest of all possible burning sequences is called optimal . Note that a new source is chosen first in each round and only later in the same round do the neighbors of the previously burned vertices become burned. A source in round t is called redundant if one of its neighbors is burned in round t-1 . In contrast to the firefighting problem, where the goal is to contain a fire, in the burning process, the aim is usually to spread an influence as quickly as possible over a network. Therefore, a natural question to ask is which sources should be chosen and in which order they need to be chosen to form an optimal burning sequence so that the entire network has received the message in as few rounds as possible. The burning number b(G) of a graph G is the minimum number of rounds needed to burn the entire graph with the burning process. Example 2.3 . Consider the graph G=(V(G),E(G)) in Figure 3 . The propagation of the burning process with burning sequence S=(v_{2},v_{5},v_{8}) is shown. In the first round, only v_{2} is burned, indicated with deep red. In the second round, first v_{5} gets burned and then the neighbors of v_{2} get burned, indicated with light red. In the third round, all the entire graphs is burned. In fact, the burning number of G is b(G)=3 which means that S is an optimal burning sequence. Note that S is not a unique optimal burning sequence in this case as S^{\prime}=(v_{6},v_{1},v_{5}) is also a burning sequence of length 3. \displaystyle v_{1} \displaystyle v_{5} \displaystyle v_{4} \displaystyle v_{2} \displaystyle v_{6} \displaystyle v_{3} \displaystyle v_{8} \displaystyle v_{7} (a) t=1 \displaystyle v_{1} \displaystyle v_{5} \displaystyle v_{4} \displaystyle v_{2} \displaystyle v_{6} \displaystyle v_{3} \displaystyle v_{8} \displaystyle v_{7} (b) t=2 \displaystyle v_{1} \displaystyle v_{5} \displaystyle v_{4} \displaystyle v_{2} \displaystyle v_{6} \displaystyle v_{3} \displaystyle v_{8} \displaystyle v_{7} (c) t=3 Figure 3 : Graph burning process for the first three rounds with burned vertices marked in red and sources are highlighted in deep red. Finding the burning number by checking every possible burning sequence could work for smaller graphs, but it becomes increasingly more difficult as the number of vertices grows. There exist other methods for finding the burning number of a graph that do not involve trying every possible burning sequence. For that, other characterizations of the burning number are used. In a graph G , observe that when a vertex v_{i} is chosen as the source in round ii all vertices in N_{j-i}[v_{i}] are burned considering b(G)\geq j . Additionally, if a vertex is burned in round i , it cannot be chosen as the source in any round i