The zero forcing number of graphs

Thomas Kalinowski, Nina Kamcev, Benny Sudakov

Research output: Contribution to journalArticleResearchpeer-review

31 Citations (Scopus)

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 languageEnglish
Pages (from-to)95-115
Number of pages21
JournalSIAM Journal on Discrete Mathematics
Volume33
Issue number1
DOIs
Publication statusPublished - 1 Jan 2019
Externally publishedYes

Keywords

  • Graphs with large girth
  • Random graphs
  • Zero forcing sets

Cite this