×

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
PDFBibTeX XMLCite
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.; 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; D. Burgarth, K. Maruyama, Indirect Hamiltonian identification through a small gateway, arXiv:0903.0612v1
[7] S. Butler, L. DeLoss, J. Grout, H.T. Hall, T. McKay, J. Smith, G. Tims, Minimum Rank Library (Sage<http://sage.cs.drake.edu/home/pub/67/>; S. Butler, L. DeLoss, J. Grout, H.T. Hall, T. McKay, J. Smith, G. Tims, Minimum Rank Library (Sage<http://sage.cs.drake.edu/home/pub/67/>
[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. 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.