×

An upper bound for the minimum rank of a graph. (English) Zbl 1144.05314

Summary: For a graph \(G\) of order \(n\), the minimum rank of \(G\) is defined to be the smallest possible rank over all real symmetric \(n\times n\) matrices \(A\) whose \((i,j)\)th entry (for \(i\neq j\)) is nonzero whenever \(\{i,j\}\) is an edge in \(G\) and is zero otherwise. We prove an upper bound for minimum rank in terms of minimum degree of a vertex is valid for many graphs, including all bipartite graphs, and conjecture this bound is true over for all graphs, and prove a related bound for all zero-nonzero patterns of (not necessarily symmetric) matrices. Most of the results are valid for matrices over any infinite field, but need not be true for matrices over finite fields.

MSC:

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

References:

[1] AIM minimum rank – special graphs work group (Francesco Barioli, Wayne Barrett, Steve Butler, Sebastian M. Cioabă, Dragoš Cvetković, Shaun M. Fallat, Chris Godsil, Willem Haemers, Leslie Hogben, Rana Mikkelson, Sivaram Narayan, Olga Pryporova, Irene Sciriha, Wasin So, Dragan Stevanović, Hein van der Holst, Kevin Vander Meulen, Amy Wangsness), Zero forcing sets and the minimum rank of graphs, Linear Algebra Appl., 428 (2008) 1628-1648.; AIM minimum rank – special graphs work group (Francesco Barioli, Wayne Barrett, Steve Butler, Sebastian M. Cioabă, Dragoš Cvetković, Shaun M. Fallat, Chris Godsil, Willem Haemers, Leslie Hogben, Rana Mikkelson, Sivaram Narayan, Olga Pryporova, Irene Sciriha, Wasin So, Dragan Stevanović, Hein van der Holst, Kevin Vander Meulen, Amy Wangsness), Zero forcing sets and the minimum rank of graphs, Linear Algebra Appl., 428 (2008) 1628-1648.
[2] American Institute of Mathematics, Minimum Rank Graph Catalog: Families of Graphs, Version: April 6, 2007. <http://aimath.org/pastworkshops/catalog2.html>; Minimum Rank Graph Catalog: Small Graphs, Version: April 11, 2007. <http://aimath.org/pastworkshops/catalog1.html>.; American Institute of Mathematics, Minimum Rank Graph Catalog: Families of Graphs, Version: April 6, 2007. <http://aimath.org/pastworkshops/catalog2.html>; Minimum Rank Graph Catalog: Small Graphs, Version: April 11, 2007. <http://aimath.org/pastworkshops/catalog1.html>.
[3] 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
[4] 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
[5] Richard Brualdi, Leslie Hogben, Bryan Shader, AIM Workshop Spectra of Families of Matrices described by Graphs, Digraphs, and Sign Patterns, Final Report: Mathematical Results (Revised). <http://aimath.org/pastworkshops/matrixspectrumrep.pdf>.; Richard Brualdi, Leslie Hogben, Bryan Shader, AIM Workshop Spectra of Families of Matrices described by Graphs, Digraphs, and Sign Patterns, Final Report: Mathematical Results (Revised). <http://aimath.org/pastworkshops/matrixspectrumrep.pdf>.
[6] DeAlba, L. M.; Hardy, T. L.; Hentzel, I. R.; Hogben, L.; Wangsness, A., Minimum rank and maximum eigenvalue multiplicity of symmetric tree sign patterns, Linear Algebra Appl., 418, 389-415 (2006) · Zbl 1106.05059
[7] Fallat, Shaun; Hogben, Leslie, The minimum rank of symmetric matrices described by a graph: a survey, Linear Algebra Appl., 426, 558-582 (2007) · Zbl 1122.05057
[8] C.R. Johnson, R. Loewy, P.A. Smith. The graphs for which maximum multiplicity of an eigenvalue is two, preprint. Available from: <http://arxiv.org/pdf/math.CO/0701562>.; C.R. Johnson, R. Loewy, P.A. Smith. The graphs for which maximum multiplicity of an eigenvalue is two, preprint. Available from: <http://arxiv.org/pdf/math.CO/0701562>.
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.