2018/01/26 by Kirk Boyer, Boris Brimkov, Sean English +6 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics #Discrete mathematics #Forcing (mathematics) #Geometric and Algebraic Topology #Graph #Graph theory and applications #Mathematical analysis #Mathematics #Polynomial #Zero (linguistics) #acm:05C15 #acm:05C31 #math.CO #msc:05C15 #msc:05C31
paper · pdf · doi:10.1016/j.dam.2018.11.033
published as Discrete Applied Mathematics, Volume 258, 2019, Pages 35-48, ISSN 0166-218X · 23 pages
arxiv created 2018/01/26 · openalex publication_date 2018/12/18 · arxiv updated 2019/05/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Zero forcing is an iterative graph coloring process, where given a set of initially colored vertices, a colored vertex with a single uncolored neighbor causes that neighbor to become colored. A zero forcing set is a set of initially colored vertices which causes the entire graph to eventually become colored. In this paper, we study the counting problem associated with zero forcing. We introduce the zero forcing polynomial of a graph G of order n as the polynomial Z(G;x)=∑i=1n z(G;i) xi, where z(G;i) is the number of zero forcing sets of G of size i. We characterize the extremal coefficients of Z(G;x), derive closed form expressions for the zero forcing polynomials of several families of graphs, and explore various structural properties of Z(G;x), including multiplicativity, unimodality, and uniqueness.