Skip to main content
Article
Propagation time for zero forcing on a graph
Discrete Applied Mathematics
  • Leslie Hogben, Iowa State University
  • My Huynh, Arizona State University
  • Nicole Kingsley, Iowa State University
  • Sarah Meyer, Smith College
  • Shanise Walker, University of Georgia
  • Michael Young, Iowa State University
Document Type
Article
Publication Version
Accepted Manuscript
Publication Date
9-1-2012
DOI
10.1016/j.dam.2012.04.003
Abstract

Zero forcing (also called graph infection) on a simple, undirected graph G is based on the color-change rule: if each vertex of G is colored either white or black, and vertex v is a black vertex with only one white neighbor w, then change the color of w to black. A minimum zero forcing set is a set of black vertices of minimum cardinality that can color the entire graph black using the color change rule. The propagation time of a zero forcing set B of graph G is the minimum number of steps that it takes to force all the vertices of G black, starting with the vertices in B black and performing independent forces simultaneously. The minimum and maximum propagation times of a graph are taken over all minimum zero forcing sets of the graph. It is shown that a connected graph of order at least two has more than one minimum zero forcing set realizing minimum propagation time. Graphs G having extreme minimum propagation times |G|−1, |G|−2, and 0 are characterized, and results regarding graphs having minimum propagation time 1 are established. It is shown that the diameter is an upper bound for maximum propagation time for a tree, but in general propagation time and diameter of a graph are not comparable.

Comments

This is a manuscript of an article from Discrete Applied Mathematics 26 (2012): 1994, doi:10.1016/j.dam.2012.04.003. Posted with permission.

Rights
This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
Copyright Owner
Elsevier B.V.
Language
en
File Format
application/pdf
Citation Information
Leslie Hogben, My Huynh, Nicole Kingsley, Sarah Meyer, et al.. "Propagation time for zero forcing on a graph" Discrete Applied Mathematics Vol. 160 (2012) p. 1994 - 2004
Available at: http://works.bepress.com/leslie-hogben/37/