Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
maximum nullity; zero forcing number; positive zero forcing number; line graphs; matrix; tree; positive semidefinite matrix; unicyclic graph
maximum nullity; zero forcing number; positive zero forcing number; line graphs; matrix; tree; positive semidefinite matrix; unicyclic graph
Summary:
The maximum nullity over a collection of matrices associated with a graph has been attracting the attention of numerous researchers for at least three decades. Along these lines various zero forcing parameters have been devised and utilized for bounding the maximum nullity. The maximum nullity and zero forcing number, and their positive counterparts, for general families of line graphs associated with graphs possessing a variety of specific properties are analysed. Building upon earlier work, where connections to the minimum rank of line graphs were established, we verify analogous equations in the positive semidefinite cases and coincidences with the corresponding zero forcing numbers. Working beyond the case of trees, we study the zero forcing number of line graphs associated with certain families of unicyclic graphs.
References:
[1] Group, AIM Minimum Rank -- Special Graphs Work: Zero forcing sets and the minimum rank of graphs. Linear Algebra Appl. 428 (2008), 1628-1648. MR 2388646
[2] Alinaghipour, F.: Zero Forcing Set for Graphs. PhD Dissertation, University of Regina (2013). MR 4272166
[3] Barioli, F., Barrett, W., Fallat, S., Hall, H. T., Hogben, L., Shader, B., Driessche, P. van den, Holst, H. van der: Zero forcing parameters and minimum rank problems. Linear Algebra Appl. 433 (2010), 401-411. MR 2645093
[4] Barioli, F., Fallat, S., Hogben, L.: On the difference between the maximum multiplicity and path cover number for tree-like graphs. Linear Algebra Appl. 409 (2005), 13-31. MR 2169544 | Zbl 1072.05037
[5] M. Booth, P. Hackney, B. Harris, C. R. Johnson, M. Lay, L. H. Mitchell, S. K. Narayan, A. Pascoe, K. Steinmetz, B. D. Sutton, W. Wang: On the minimum rank among positive semidefinite matrices with a given graph. SIAM J. Matrix Anal. Appl. 30 (2008), 731-740. DOI 10.1137/050629793 | MR 2421468
[6] 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. 436 (2012), 4352-4372. MR 2917414 | Zbl 1241.05076
[7] J. Ekstrand, C. Erickson, H. T. Hall, D. Hay, L. Hogben, R. Johnson, N. Kingsley, S. Osborne, T. Peters, J. Roat, A. Ross, D. D. Row, N. Warnberg, M. Young: Positive semidefinite zero forcing. Linear Algebra Appl. 439 (2013), 1862-1874. MR 3090441
[8] Ekstrand, J., Erickson, C., Hay, D., Hogben, L., Roat, J.: Note on positive semidefinite maximum nullity and positive semidefinite zero forcing number of partial $2$-trees. Electron. J. Linear Algebra. (electronic only) 23 (2012), 79-87. MR 2889573 | Zbl 1252.05118
[9] Eroh, L., Kang, C. X., Yi, E.: A Comparison between the Metric Dimension and Zero Forcing Number of Line Graphs. (2012), 14 pages arXiv:1207.6127v1 [math.CO]. MR 3027310
[10] Fallat, S. M., Hogben, L.: Chapter 46: Minimum rank, maximum nullity, and zero forcing number of graphs. Handbook of Linear Algebra L. Hogben CRC Press, Boca Raton (2014), 46-1-46-36. MR 3141806
[11] Fallat, S., Hogben, L.: The minimum rank of symmetric matrices described by a graph: a survey. Linear Algebra Appl. 426 (2007), 558-582. MR 2350678 | Zbl 1122.05057
[12] Nylen, P. M.: Minimum-rank matrices with prescribed graph. Linear Algebra Appl. 248 (1996), 303-316. MR 1416462 | Zbl 0864.05069
[13] Owens, K.: Properties of the Zero Forcing Number. Master's Thesis, Brigham Young University (2009).
[14] Peters, T.: Positive semidefinite maximum nullity and zero forcing number. Electron. J. Linear Algebra (electronic only) 23 (2012), 815-830. MR 2992396 | Zbl 1252.05130
[15] Row, D. D.: A technique for computing the zero forcing number of a graph with a cut-vertex. Linear Algebra Appl. 436 (2012), 4423-4432. MR 2917419 | Zbl 1241.05086
[16] Yu, X.: Cyclomatic numbers of connected induced subgraphs. Discrete Math. 105 (1992), 275-284. DOI 10.1016/0012-365X(92)90150-E | MR 1180211 | Zbl 0783.05065
Search
Partner of
