Skip to main content
Families of graphs with maximum nullity equal to zero forcing number
Special Matrices
  • Joseph S. Alameda, Iowa State University
  • Emelie Curl, Iowa State University
  • Armando Grez, Iowa State University
  • Leslie Hogben, Iowa State University
  • O'Neill Kingston, Iowa State University
  • Alex Schulte, Iowa State University
  • Derek Young, Iowa State University
  • Michael Young, Iowa State University
Document Type
Publication Version
Published Version
Publication Date
The maximum nullity of a simple graph G, denoted M(G), is the largest possible nullity over all symmetric real matrices whose ijth entry is nonzero exactly when fi, jg is an edge in G for i =6 j, and the iith entry is any real number. The zero forcing number of a simple graph G, denoted Z(G), is the minimum number of blue vertices needed to force all vertices of the graph blue by applying the color change rule. This research is motivated by the longstanding question of characterizing graphs G for which M(G) = Z(G). The following conjecture was proposed at the 2017 AIM workshop Zero forcing and its applications: If G is a bipartite 3- semiregular graph, then M(G) = Z(G). A counterexample was found by J. C.-H. Lin but questions remained as to which bipartite 3-semiregular graphs have M(G) = Z(G). We use various tools to find bipartite families of graphs with regularity properties for which the maximum nullity is equal to the zero forcing number; most are bipartite 3-semiregular. In particular, we use the techniques of twinning and vertex sums to form new families of graphs for which M(G) = Z(G) and we additionally establish M(G) = Z(G) for certain Generalized Petersen graphs.

This article is published as Alameda, Joseph S., Emelie Curl, Armando Grez, Leslie Hogben, Alex Schulte, Derek Young, and Michael Young. "Families of graphs with maximum nullity equal to zero forcing number." Special Matrices 6, no. 1 (2018): 56-67. DOI: 10.1515/spma-2018-0006. Posted with permission.

Creative Commons License
Creative Commons Attribution-Noncommercial-No Derivative Works 4.0
Copyright Owner
The Authors
File Format
Citation Information
Joseph S. Alameda, Emelie Curl, Armando Grez, Leslie Hogben, et al.. "Families of graphs with maximum nullity equal to zero forcing number" Special Matrices Vol. 6 Iss. 1 (2018) p. 56 - 67
Available at: