Skip to main content
Article
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
Article
Publication Version
Published Version
Publication Date
2-2-2018
DOI
10.1515/spma-2018-0006
Abstract

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.

Comments

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 International
Copyright Owner
The Authors
Language
en
File Format
application/pdf
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: http://works.bepress.com/leslie-hogben/82/