×

zbMATH — the first resource for mathematics

Vertex and edge spread of zero forcing number, maximum nullity, and minimum rank of a graph. (English) Zbl 1241.05076
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; maximum nullity is taken over the same set of matrices.
The zero forcing number is the minimum size of a zero forcing set of vertices and bounds the maximum nullity from above. The spread of a graph parameter at a vertex \(v\) or edge \(e\) of \(G\) is the difference between the value of the parameter on \(G\) and on \(G-v\) or \(G-e\). Rank spread (at a vertex) was introduced in [F. Barioli, S. M. Fallar and I. Hogben, Linear Algebra Appl. 392, 289–303 (2004; Zbl 1052.05045)].
This paper introduces vertex spread of the zero forcing number and edge spreads for minimum rank/maximum nullity and zero forcing number. Properties of the spreads are established and used to determine values of the minimum rank/maximum nullity and zero forcing number for various types of grids with a vertex or edge deleted.

MSC:
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
15A03 Vector spaces, linear dependence, rank, lineability
15A18 Eigenvalues, singular values, and eigenvectors
Citations:
Zbl 1052.05045
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Barioli, F.; Barrett, W.; Butler, S.; Cioabă, S.M.; Cvetković, D.; Fallat, S.M.; Godsil, C.; Haemers, W.; Hogben, L.; Mikkelson, R.; Narayan, S.; Pryporova, O.; Sciriha, I.; So, W.; Stevanović, D.; van der Holst, H.; Vander Meulen, K.; Wangsness, A., Zero forcing sets and the minimum rank of graphs, Linear algebra appl., 428, 7, 1628-1648, (2008) · Zbl 1135.05035
[2] Barioli, F.; Barrett, W.; Fallat, S.M.; Hall, H.T.; Hogben, L.; Shader, B.; van den Driessche, P.; van der Holst, H., Zero forcing parameters and minimum rank problems, Linear algebra appl., 433, 401-411, (2010) · Zbl 1209.05139
[3] Barioli, F.; Fallat, S.M.; Hall, H.T.; Hershkowitz, D.; Hogben, L.; van der Holst, H.; Shader, B., On the minimum rank of not necessarily symmetric matrices: a preliminary study, Electron. J. linear algebra, 18, 126-145, (2009) · Zbl 1169.05345
[4] Barioli, F.; Fallat, S.M.; Hogben, L., Computation of minimal rank and path cover number for graphs, Linear algebra appl., 392, 289-303, (2004) · Zbl 1052.05045
[5] Barioli, F.; Fallat, S.M.; 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
[6] W. Barrett, H.T. Hall, H. van der Holst, J. Sinkovic, The minimum rank problem for rectangular grids, preprint.
[7] Colin de Verdière, Y., Multiplicities of eigenvalues and tree-width of graphs, J. combin. theory ser. B, 74, 121-146, (1998) · Zbl 1027.05064
[8] L. DeLoss, J. Grout, T. McKay, J. Smith, G. Tims, ISU minimum rank program, Faster zero forcing number program by J. Grout available from L. Hogben. Available at <http://arxiv.org/abs/0812.1616>.
[9] DeLoss, L.; Grout, J.; Hogben, L.; McKay, T.; Smith, J.; Tims, G., Techniques for determining the minimum rank of a small graph, Linear algebra appl., 432, 2005-3001, (2010) · Zbl 1195.05041
[10] Fallat, S.M.; Hogben, L., The minimum rank of symmetric matrices described by a graph: a survey, Linear algebra appl., 426, 558-582, (2007) · Zbl 1122.05057
[11] Hogben, L., Minimum rank problems, Linear algebra appl., 432, 1961-1974, (2010) · Zbl 1213.05036
[12] Huang, L.-H.; Chang, G.J.; Yeh, H.-G., On minimum rank and zero forcing sets of a graph, Linear algebra appl., 432, 2961-2973, (2010) · Zbl 1195.05043
[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, 139-144, (1999) · Zbl 0929.15005
[14] Nylen, P.M., Minimum-rank matrices with prescribed graph, Linear algebra appl., 248, 303-316, (1996) · Zbl 0864.05069
[15] Sinkovic, John, Maximum corank of outerplanar graphs and the path cover number, Linear algebra appl., 432, 2052-2060, (2010) · Zbl 1201.05061
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.