×

zbMATH — the first resource for mathematics

A technique for computing the zero forcing number of a graph with a cut-vertex. (English) Zbl 1241.05086
Summary: The zero forcing number of a graph is the minimum size of a zero forcing set. This parameter is useful in the minimum rank/maximum nullity problem, as it gives an upper bound to the maximum nullity. Results for determining graphs with extreme zero forcing numbers, for determining the zero forcing number of graphs with a cut-vertex, and for determining the zero forcing number of unicyclic graphs are presented.

MSC:
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
15A03 Vector spaces, linear dependence, rank, lineability
05C38 Paths and cycles
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] AIM Minimum Rank - Special Graphs Work Group (F. Barioli, W. Barrett, S. Butler, S.M. Cioabă, D. Cvetković, S.M. Fallat, C. Godsil, W. Haemers, L. Hogben, R. Mikkelson, S. Narayan, O. Pryporova, I. Sciriha, W. So, D. Stevanović, H. van der Holst, K. Vander Meulen, A. Wangsness), Zero forcing sets and the minimum rank of graphs, Linear Algebra Appl. 428/7 (2008) 1628-1648. · Zbl 1135.05035
[2] Barioli, F.; Barrett, W.; Fallat, S.; 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.; Hershkowitz, D.; Hall, H.T.; 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.; Fallet, S.; Hogben, L., On the difference between the maximum multiplicity and path cover number for tree-like graphs, Linear algebra appl., 409, 13-31, (2005) · Zbl 1072.05037
[5] Burgarth, D.; Giovannetti, V., Full control by locally induced relaxation, Phys. rev. lett., 99, 100501, (2007)
[6] D. Burgarth, K. Maruyama, Indirect Hamiltonian identification through a small gateway, arXiv:0903.0612v1 [quant-ph], 2009.
[7] S. Butler, L. DeLoss, J. Grout, H.T. Hall, T. McKay, J. Smith, G. Tims, Minimum Rank Library (Sage programs for calculating bounds on the minimum rank of a graph, and for computing zero forcing parameters). Available at <http://sage.cs.drake.edu/home/pub/67/>, For more information contact Jason Grout at jason.grout@drake.edu.
[8] Edholm, C.J.; Hogben, L.; Huynh, M.; LaGrange, J.; Row, D.D., Vertex and edge spread of zero forcing number, maximum nullity, and minimum rank of a graph, Linear algebra appl., (2010) · Zbl 1241.05076
[9] 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
[10] Hogben, L., Minimum rank problems, Linear algebra appl., 432, 1961-1974, (2010) · Zbl 1213.05036
[11] 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
[12] Johnson, C.R.; Loewy, R.; Smith, P.A., The graphs for which the maximum multiplicity of an eigenvalue is two, Linear and multilinear algebra, 57, 713-736, (2009) · Zbl 1225.05167
[13] Severini, S., Nondiscriminatory propogation on trees, J. phys. A, 41, 482002, (2008) · Zbl 1156.81357
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.