×

Zero forcing sets and the minimum rank of graphs. (English) Zbl 1135.05035

Summary: The minimum rank of a simple graph \(G\) is defined to be the smallest possible rank over all symmetric real matrices whose \(ij\)th entry (for \(i\neq j\)) is nonzero whenever \(\{i,j\}\) is an edge in \(G\) and is zero otherwise. This paper introduces a new graph parameter, \(Z(G)\), that is the minimum size of a zero forcing set of vertices and uses it to bound the minimum rank for numerous families of graphs, often enabling computation of the minimum rank.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
15A18 Eigenvalues, singular values, and eigenvectors
15A03 Vector spaces, linear dependence, rank, lineability
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] American Institute of Mathematics. Minimum rank graph catalog. <http://aimath.org/pastworkshops/matrixspectrum.html>; American Institute of Mathematics. Minimum rank graph catalog. <http://aimath.org/pastworkshops/matrixspectrum.html>
[2] Barioli, F.; Fallat, S.; Hogben, L., Computation of minimal rank and path cover number for graphs, Linear Algebra Appl., 392, 289-303 (2004) · Zbl 1052.05045
[3] Barioli, F.; Fallat, S.; Hogben, L., A variant on the graph parameters of Colin de Verdière: implications to the minimum rank of graphs, Electron. J. Linear Algebra, 13, 387-404 (2005) · Zbl 1092.05042
[4] W. Barrett, J. Grout, R. Loewy, The minimum rank problem over the finite field of order 2: minimum rank 3. <http://arxiv.org/abs/math.co/0612331>; W. Barrett, J. Grout, R. Loewy, The minimum rank problem over the finite field of order 2: minimum rank 3. <http://arxiv.org/abs/math.co/0612331> · Zbl 1194.05080
[5] Barrett, W.; van der Holst, H.; Loewy, R., Graphs whose minimal rank is two, Electron. J. Linear Algebra, 11, 258-280 (2004) · Zbl 1070.05059
[6] M. Booth, P. Hackney, B. Harris, C.R. Johnson, M. Lay, L.H. Mitchell, S.K. Narayan, A. Pascoe, K. Steinmetz, B.D. Sutton, W. Wang, On the minimum rank among positive semidefinite matrices with a given graph, preprint.; M. Booth, P. Hackney, B. Harris, C.R. Johnson, M. Lay, L.H. Mitchell, S.K. Narayan, A. Pascoe, K. Steinmetz, B.D. Sutton, W. Wang, On the minimum rank among positive semidefinite matrices with a given graph, preprint. · Zbl 1226.05151
[7] Chenette, N. L.; Droms, S. V.; Hogben, L.; Mikkelson, R.; Pryporova, O., Minimum rank of a tree over an arbitrary field, Electron. J. Linear Algebra, 16, 183-186 (2007) · Zbl 1142.05335
[8] Fallat, S.; Hogben, L., The minimum rank of symmetric matrices described by a graph: a survey, Linear Algebra Appl., 426, 558-582 (2007) · Zbl 1122.05057
[9] Godsil, C.; Royle, G., Algebraic Graph Theory (2001), Springer-Verlag: Springer-Verlag New York · Zbl 0968.05002
[10] Hald, O. H., Inverse eigenvalue problems for Jacobi matrices, Linear Algebra Appl., 14, 635 (1976)
[11] Hogben, L.; van der Holst, H., Forbidden minors for the class of graphs \(G\) with \(\xi(G) \leqslant 2\), Linear Algebra Appl., 423, 42-52 (2007) · Zbl 1118.05064
[12] H. van der Holst, Three-connected graphs whose maximum corank is at most three, preprint.; H. van der Holst, Three-connected graphs whose maximum corank is at most three, preprint. · Zbl 1145.05037
[13] Johnson, C. R.; Leal Duarte, A., The maximum multiplicity of an eigenvalue in a matrix whose graph is a tree, Linear and Multilinear Algebra, 46, 39-144 (1999) · Zbl 0929.15005
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.