The zero forcing polynomial of a graph
arXiv:1801.08910 · doi:10.1016/j.dam.2018.11.033
Abstract
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 of order as the polynomial , where is the number of zero forcing sets of of size . We characterize the extremal coefficients of , derive closed form expressions for the zero forcing polynomials of several families of graphs, and explore various structural properties of , including multiplicativity, unimodality, and uniqueness.
arXiv comment23 pages
References in corpus (7)
- Full control by locally induced relaxation
- Propagation time for zero forcing on a graph
- Zero forcing, linear and quantum controllability for systems evolving on networks
- Logic circuits from zero forcing
- Throttling positive semidefinite zero forcing propagation time on graphs
- Fractional Zero Forcing via Three-color Forcing Games
- Domination polynomials of k-tree related graphs