Abstract
A subset S of initially infected vertices of a graph G is called zero forcing if we can infect the entire graph by iteratively applying the following process. At each step, any infected vertex which has a unique uninfected neighbor, infects this neighbor. The zero forcing number of G is the minimum cardinality of a zero forcing set in G. We study the zero forcing number of various classes of graphs, including graphs of large girth, H-free graphs for a fixed bipartite graph H, and random and pseudorandom graphs.
Original language | English |
---|---|
Pages (from-to) | 95-115 |
Number of pages | 21 |
Journal | SIAM Journal on Discrete Mathematics |
Volume | 33 |
Issue number | 1 |
DOIs | |
Publication status | Published - 1 Jan 2019 |
Externally published | Yes |
Keywords
- Graphs with large girth
- Random graphs
- Zero forcing sets