Vol. 8, No. 1, 2015

Download this article
Download this article For screen
For printing
Recent Issues

Volume 10
Issue 5, 721–900
Issue 4, 541–720
Issue 3, 361–539
Issue 2, 181–360
Issue 1, 1–180

Volume 9, 5 issues

Volume 8, 5 issues

Volume 7, 6 issues

Volume 6, 4 issues

Volume 5, 4 issues

Volume 4, 4 issues

Volume 3, 4 issues

Volume 2, 5 issues

Volume 1, 2 issues

The Journal
Cover Page
Editorial Board
Editors’ Addresses
Editors’ Interests
About the Journal
Scientific Advantages
Submission Guidelines
Submission Form
Ethics Statement
Subscriptions
Editorial Login
Author Index
Coming Soon
Contacts
 
ISSN: 1944-4184 (e-only)
ISSN: 1944-4176 (print)
The failed zero forcing number of a graph

Katherine Fetcie, Bonnie Jacob and Daniel Saavedra

Vol. 8 (2015), No. 1, 99–117
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