×

Maximum nullity and zero forcing of circulant graphs. (English) Zbl 1457.05063

Summary: The zero forcing number of a graph has been applied to communication complexity, electrical power grid monitoring, and some inverse eigenvalue problems. It is well-known that the zero forcing number of a graph provides a lower bound on the minimum rank of a graph. In this paper we bound and characterize the zero forcing number of various circulant graphs, including families of bipartite circulants, as well as all cubic circulants. We extend the definition of the Möbius ladder to a type of torus product to obtain bounds on the minimum rank and the maximum nullity on these products. We obtain equality for torus products by employing orthogonal Hankel matrices. In fact, in every circulant graph for which we have determined these numbers, the maximum nullity equals the zero forcing number. It is an open question whether this holds for all circulant graphs.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C75 Structural characterization of families of graphs
05C76 Graph operations (line graphs, products, etc.)
15A03 Vector spaces, linear dependence, rank, lineability

Software:

GitHub

References:

[1] A. Aazami, Hardness results and approximation algorithms for some problems on graphs, PhD thesis, University of Waterloo, 2008. http://hdl.handle.net/10012/4147.
[2] AIM minimum rank - special graphs work group, Zero forcing sets and the minimum rank of graphs. Linear Algebra Appl.428 (2008), 1628-1648. · Zbl 1135.05035
[3] J.S. Alameda, E. Curl, A. Grez, L. Hogben, A. Schulte, D. Young, and M. Young, Families of graphs with maximum nullity equal to zero forcing number. Spec. Matrices6:1 (2018), 56-67. · Zbl 1391.05157
[4] W. Barrett, H. Van Der Holst, and R. Loewy, Graphs whose minimal rank is two. Electron. J. Linear Algebra11 (2004), 258-280. · Zbl 1070.05059
[5] K.F. Benson, D. Ferrero, M. Flagg, V. Furst, L. Hogben, V. Vasilevska, and B. Wissman, Zero forcing and power domination for graph products. Australas. J. Combin.70(2) (2018), 221-235. · Zbl 1383.05225
[6] F. Boesch, R. Tindell, Circulants and their connectivities. J. Graph Theory8 (1984), 487-499. · Zbl 0549.05048
[7] R. Davila, T. Kalinowski, S. Stephen, A lower bound on the zero forcing number. Discrete Appl. Math.250 (2018), 363-367. · Zbl 1398.05083
[8] R. Davila, F. Kenter, Bounds for the zero forcing number of graphs with large girth. Theory Appl. Graphs2 (2015), Art. 1, 8 pp. · Zbl 1416.05169
[9] G. Davis, G. Domke, 3-Circulant graphs. J. Combin. Math. Combin. Comput.40 (2002), 133-142. · Zbl 0989.05075
[10] L. Deaett, S. Meyer, The minimum rank problem for circulants. Linear Algebra Appl.491 (2016), 386-418. · Zbl 1330.05099
[11] L. DeAlba, J. Grout, L. Hogben, R. Mikkelson, and K. Rasmussen, Universally optimal matrices and field independence of the minimum rank of a graph. Electron. J. Linear Algebra 18 (2009) 403-419. · Zbl 1189.05100
[12] L. Duong, B.K. Kroschel, Zero Forcing Number (2010). Preprint.
[13] B. Eastman, A LATEX program for creating circulant graphs, GitHub Repository. Available online https://github.com/brydon-zz/circulant, 2014.
[14] S. Fallat, L. Hogben, Minimum rank, maximum nullity, and zero forcing number of graphs. In Handbook of Linear Algebra, 2nd edition, L. Hogben editor, CRC Press, Boca Raton, 2014.
[15] C. Heuberger, On planarity and colorability of circulant graphs. Discrete Math. 268 (2003), 153-169. · Zbl 1028.05024
[16] L. Hogben, W. Barrett, J. Grout, H. van der Holst, K. Rasmussen, A. Smith, and D. Young. AIM minimum rank graph catalog, 2016. http://admin.aimath.org/resources/graph-invariants/minimumrankoffamilies/#/cuig.
[17] A. Márquez, A. de Mier, M. Noy, and M.P. Revuelta, Locally grid graphs: classification and Tutte uniqueness. Discrete Math.266 (2003), 327-352. · Zbl 1032.05038
[18] S. Meyer, Zero forcing sets and bipartite circulants. Linear Algebra Appl.436 (2012), 888-900. · Zbl 1236.05163
[19] M. Muzychuk, Ádám’s conjecture is true in the square-free case. J. Combin. Theory Ser. A72 (1995), 118-134. · Zbl 0833.05063
[20] M. Riddell, The zero forcing number of circulant graphs. MSc Project, McMaster University (2017).
[21] D. West, Introduction to graph theory. Prentice Hall, Inc., Upper Saddle River, NJ, 1996. · Zbl 0845.05001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.