Campus Units

Mathematics

Document Type

Article

Publication Version

Published Version

Publication Date

2-2-2018

Journal or Book Title

Special Matrices

Volume

6

Issue

1

First Page

56

Last Page

67

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 License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.

Copyright Owner

The Authors

Language

en

File Format

application/pdf

Share

COinS