Families of graphs with maximum nullity equal to zero forcing number

Thumbnail Image
Date
2018-02-02
Authors
Alameda, Joseph
Curl, Emelie
Grez, Armando
Hogben, Leslie
Kingston, O'Neill
Schulte, Alex
Young, Derek
Young, Michael
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Authors
Research Projects
Organizational Units
Organizational Unit
Organizational Unit
Journal Issue
Is Version Of
Versions
Series
Department
Electrical and Computer EngineeringMathematics
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.

Description
Keywords
Citation
DOI
Copyright
Mon Jan 01 00:00:00 UTC 2018
Collections