Skip to main content
Article
Zero Forcing Propagation Time on Oriented Graphs
Discrete Applied Mathematics
  • Adam Berliner, Saint Olaf College
  • Chassidy Bozeman, Iowa State University
  • Steve Butler, Iowa State University
  • Minerva Catral, Xavier University
  • Leslie Hogben, Iowa State University
  • Brenda Kroschel, University of Saint Thomas
  • Jephian C.H. Lin, Iowa State University
  • Nathan Warnberg, University of Wisconsin, LaCrosse
  • Michael Young, Iowa State University
Document Type
Article
Publication Version
Submitted Manuscript
Publication Date
6-19-2017
DOI
10.1016/j.dam.2017.02.017
Abstract

Zero forcing is an iterative coloring procedure on a graph that starts by initially coloring vertices white and blue and then repeatedly applies the following rule: if any blue vertex has a unique (out-)neighbor that is colored white, then that neighbor is forced to change color from white to blue. An initial set of blue vertices that can force the entire graph to blue is called a zero forcing set. In this paper we consider the minimum number of iterations needed for this color change rule to color all of the vertices blue, also known as the propagation time, for oriented graphs. We produce oriented graphs with both high and low propagation times, consider the possible propagation times for the orientations of a fixed graph, and look at balancing the size of a zero forcing set and the propagation time.

Comments

This is a manuscript of an article published as Berliner, Adam, Chassidy Bozeman, Steve Butler, Minerva Catral, Leslie Hogben, Brenda Kroschel, Jephian C-H Lin, Nathan Warnberg, and Michael Young. "Zero forcing propagation time on oriented graphs." Discrete Applied Mathematics 224 (2017): 45-59. DOI: 10.1016/j.dam.2017.02.017. Posted with permission.

Creative Commons License
Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International
Copyright Owner
Elsevier Inc.
Language
en
File Format
application/pdf
Citation Information
Adam Berliner, Chassidy Bozeman, Steve Butler, Minerva Catral, et al.. "Zero Forcing Propagation Time on Oriented Graphs" Discrete Applied Mathematics Vol. 224 (2017) p. 45 - 59
Available at: http://works.bepress.com/leslie-hogben/33/