Computational and Theoretical Challenges for Computing the Minimum Rank of a Graph

References

• AIM Special Work Group (2008) Zero forcing sets and the minimum rank of graphs. Linear Algebra Appl. 428(7):1628–1648.Crossref, Google Scholar
• Barioli F, Fallat S (2007) On the minimum rank of the join of graphs and decomposable graphs. Linear Algebra Appl. 421:252–263.Crossref, Google Scholar
• Barioli F, Fallat S, Hogben L (2004) Computation of minimal rank and path cover number for graphs. Linear Algebra Appl. 392:289–303.Crossref, Google Scholar
• Barioli F, Fallat S, Hogben L (2005a) On the difference between the maximum multiplicity and path cover number for tree-like graphs. Linear Algebra Appl. 409:13–31.Crossref, Google Scholar
• Barioli F, Fallat S, Hogben L (2005b) A variant on the graph parameters of Colin de Verdiere: Implications to the minimum rank of graphs. Electron. J. Linear Algebra 13(1):387–404.Google Scholar
• Barioli F, Barrett W, Fallat S, Hall H, Hogben L, van der Holst H (2012) On the graph complement conjecture for minimum rank. Linear Algebra Appl. 436(12):4373–4391.Crossref, Google Scholar
• Barioli F, Barrett W, Fallat SM, Hall HT, Hogben L, Shader B, van den Driessche P, et al. (2013) Parameters related to tree-width, zero forcing, and maximum nullity of a graph. J. Graph Theory 72(2):146–177.Crossref, Google Scholar
• Barrett W, Grout J, Loewy R (2009b) The minimum rank problem over the finite field of order 2: Minimum rank 3. Linear Algebra Appl. 430(4):890–923.Crossref, Google Scholar
• Barrett W, van der Holst H, Loewy R (2004) Graphs whose minimal rank is two. Electron. J. Linear Algebra 11:258–280.Crossref, Google Scholar
• Barrett W, van der Holst H, Loewy R (2005) Graphs whose minimal rank is two: the finite fields case. Electron. J. Linear Algebra 14:32–42.Crossref, Google Scholar
• Barrett W, Bowcutt R, Cutler M, Gibelyou S, Owens K (2009a) Minimum rank of edge subdivisions of graphs. Electron. J. Linear Algebra 18(1):530–563.Google Scholar
• Barrett W, Butler S, Catral M, Fallat S, Hall HT, Hogben L, Young M (2014) The maximum nullity of a complete subdivision graph is equal to its zero forcing number. Electron. J. Linear Algebra 27(1):444–457.Google Scholar
• Brimkov B, Scherr Z (2019) An exact algorithm for the minimum rank of a graph. Preprint, submitted November 30, https://arxiv.org/abs/1912.00158.Google Scholar
• Candes E, Plan Y (2010) Matrix completion with noise. Proc. IEEE 98(6):925–936.Crossref, Google Scholar
• DeLoss L, Grout J, Hogben L, McKay T, Smith J, Tims G (2008a) Program for calculating bounds on the minimum rank of a graph using sage. Preprint, submitted December 9, https://arxiv.org/abs/0812.1616.Google Scholar
• DeLoss L, Grout J, Hogben L, McKay T, Smith J, Tims G (2008b) Table of minimum ranks of graphs of order at most 7 and selected optimal matrices. Preprint, submitted December 4, https://arxiv.org/abs/0812.0870.Google Scholar
• DeLoss L, Grout J, Hogben L, McKay T, Smith J, Tims G (2010) Techniques for determining the minimum rank of a small graph. Linear Algebra Appl. 432:2995–3001.Crossref, Google Scholar
• Edholm C, Hogben L, Huynh M, LaGrange J, Row D (2012) Vertex and edge spread of zero forcing number, maximum nullity, and minimum rank of a graph. Linear Algebra Appl. 436(12):4352–4372.Crossref, Google Scholar
• Gentner M, Penso L, Rautenbach D, Souza U (2016) Extremal values and bounds for the zero forcing number. Discrete Appl. Math. 214:196–200.Crossref, Google Scholar
• Godsil C, Severini S (2010) Control by quantum dynamics on graphs. Phys. Rev. A 81(5):052316.Crossref, Google Scholar
• Hogben L (2005) Spectral graph theory and the inverse eigenvalue problem of a graph. Electron. J. Linear Algebra 14(1):12–31.Google Scholar
• Hogben L (2008) Orthogonal representations, minimum rank, and graph complements. Linear Algebra Appl. 428:2560–2568.Crossref, Google Scholar
• Hogben L, van der Holst H (2007) Forbidden minors for the class of graphs g with ξ(g)≤2. Linear Algebra Appl. 423:42–52.Crossref, Google Scholar
• Hsieh LY (2001) On minimum rank matrices having prescribed graph. PhD thesis, University of Wisconsin, Madison.Google Scholar
• Huang L, Chang G, Yeh H (2010) On minimum rank and zero forcing sets of a graph. Linear Algebra Appl. 432(11):2961–2973.Crossref, Google Scholar
• Johnson C, Duarte A (1999) The maximum multiplicity of an eigenvalue in a matrix whose graph is a tree. Linear Multilinear Algebra 46:139–144.Crossref, Google Scholar
• Johnson C, Saiago C (2002) Estimation of the maximum multiplicity of an eigenvalue in terms of the vertex degrees of the graph of the matrix. Electron. J. Linear Algebra 9:27–31.Crossref, Google Scholar
• Johnson C, Loewy R, Smith P (2009) The graphs for which the maximum multiplicity of an eigenvalue is two. Linear Multilinear Algebra 57(7):713–736.Crossref, Google Scholar
• Koren Y (2009) The BllKor solution to the Netflix grand prize.Google Scholar
• Mahindre G, Jayasumana A, Gajamannage K, Paffenroth R (2019) On sampling and recovery of topology of directed social networks: A low-rank matrix completion based approach. Proc. IEEE Conf. on Local Computer Networks (IEEE), 324–331.Google Scholar
• Mitchell L, Narayan S, Zimmer A (2010) Lower bounds in minimum rank problems. Linear Algebra Appl. 432(1):430–440.Crossref, Google Scholar
• Nylen P (1996) Minimum-rank matrices with prescribed graph. Linear Algebra Appl. 248:303–316.Crossref, Google Scholar
• Wei P, Weng C (2001) A typical vertex of a tree. Discrete Math. 226:337–345.Crossref, Google Scholar