The failed zero forcing number of a graph

Fetcie, Katherine; Jacob, Bonnie; Saavedra, Daniel

doi:10.2140/involve.2015.8.99

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the journal

Ethics and policies

Peer-review process

Submission guidelines

ISSN 1944-4184 (online)

ISSN 1944-4176 (print)

Author index

To appear

Other MSP journals

The failed zero forcing number of a graph

Katherine Fetcie, Bonnie Jacob and Daniel Saavedra

Vol. 8 (2015), No. 1, 99–117

DOI: 10.2140/involve.2015.8.99

Abstract

Given a graph $G$ , the zero forcing number of $G$ , $Z (G)$ , is the smallest cardinality of any set $S$ of vertices on which repeated applications of the color change rule results in all vertices joining $S$ . The color change rule is: if a vertex $v$ is in $S$ , and exactly one neighbor $u$ of $v$ is not in $S$ , then $u$ joins $S$ in the next iteration.

In this paper, we introduce a new graph parameter, the failed zero forcing number of a graph. The failed zero forcing number of $G$ , $F (G)$ , is the maximum cardinality of any set of vertices on which repeated applications of the color change rule will never result in all vertices joining the set.

We establish bounds on the failed zero forcing number of a graph, both in general and for connected graphs. We also classify connected graphs that achieve the upper bound, graphs whose failed zero forcing numbers are zero or one, and unusual graphs with smaller failed zero forcing number than zero forcing number. We determine formulas for the failed zero forcing numbers of several families of graphs and provide a lower bound on the failed zero forcing number of the Cartesian product of two graphs.

We conclude by presenting open questions about the failed zero forcing number and zero forcing in general.

Keywords

zero forcing number, vertex labeling, graph coloring

Mathematical Subject Classification 2010

Primary: 05C15, 05C78, 05C57

Secondary: 05C50

Milestones

Received: 21 June 2013

Revised: 30 July 2013

Accepted: 4 August 2013

Published: 10 December 2014

Communicated by Joseph A. Gallian

Authors

Katherine Fetcie
Department of Civil Engineering Technology, Environmental Management and Safety Rochester Institute of Technology 1 Lomb Memorial Drive Rochester, NY 14623 United States

Bonnie Jacob
Science and Mathematics Department, National Technical Institute for the Deaf Rochester Institute of Technology 52 Lomb Memorial Drive Rochester, NY 14623 United States

Daniel Saavedra
Department of Packaging Science College of Applied Science and Technology Rochester Institute of Technology 1 Lomb Memorial Drive Rochester, NY 14623 United States

Vol. 8, No. 1, 2015