Department/School
Mathematics
Date
1-1-2020
Document Type
Article
Keywords
zero forcing, minimum rank, maximum nullity, circulant graph, bipartite graph, graph product
DOI
https://doi.org/10.1515/spma-2020-0106
Abstract
The zero forcing number of a graph has been applied to communication complexity, electrical powergrid monitoring, and some inverse eigenvalue problems. It is well-known that the zero forcing number of agraph provides a lower bound on the minimum rank of a graph. In this paper we bound and characterizethe zero forcing number of various circulant graphs, including families of bipartite circulants, as well as allcubic circulants. We extend the de nition of the Möbius ladder to a type of torus product to obtain boundson the minimum rank and the maximum nullity on these products. We obtain equality for torus products byemploying orthogonal Hankel matrices. In fact, in every circulant graph for which we have determined thesenumbers, the maximum nullity equals the zero forcing number. It is an open question whether this holds forall circulant graphs.
Published in
Special Matrices
Citation/Other Information
Duong, L., Kroschel, B. K., Riddell, M., Vander Meulen, K. N., & Van Tuyl, A. (2020). Maximum nullity and zero forcing of circulant graphs. Special Matrices, 8(1), 221–234. https://doi.org/10.1515/spma-2020-0106