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.

Volume

8

Issue

1

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

Included in

Mathematics Commons

COinS