Line graphs: their maximum nullities and zero forcing numbers

Shaun Fallat; Abolghasem Soltani

Czechoslovak Mathematical Journal (2016)

  • Volume: 66, Issue: 3, page 743-755
  • ISSN: 0011-4642

Abstract

top
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.

How to cite

top

Fallat, Shaun, and Soltani, Abolghasem. "Line graphs: their maximum nullities and zero forcing numbers." Czechoslovak Mathematical Journal 66.3 (2016): 743-755. <http://eudml.org/doc/286812>.

@article{Fallat2016,
abstract = {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.},
author = {Fallat, Shaun, Soltani, Abolghasem},
journal = {Czechoslovak Mathematical Journal},
keywords = {maximum nullity; zero forcing number; positive zero forcing number; line graphs; matrix; tree; positive semidefinite matrix; unicyclic graph},
language = {eng},
number = {3},
pages = {743-755},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Line graphs: their maximum nullities and zero forcing numbers},
url = {http://eudml.org/doc/286812},
volume = {66},
year = {2016},
}

TY - JOUR
AU - Fallat, Shaun
AU - Soltani, Abolghasem
TI - Line graphs: their maximum nullities and zero forcing numbers
JO - Czechoslovak Mathematical Journal
PY - 2016
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 66
IS - 3
SP - 743
EP - 755
AB - 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.
LA - eng
KW - maximum nullity; zero forcing number; positive zero forcing number; line graphs; matrix; tree; positive semidefinite matrix; unicyclic graph
UR - http://eudml.org/doc/286812
ER -

References

top
  1. Group, AIM Minimum Rank -- Special Graphs Work, Zero forcing sets and the minimum rank of graphs, Linear Algebra Appl. 428 (2008), 1628-1648. (2008) MR2388646
  2. Alinaghipour, F., Zero Forcing Set for Graphs, PhD Dissertation, University of Regina (2013). (2013) 
  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. (2010) MR2645093
  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. (2005) Zbl1072.05037MR2169544
  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, 10.1137/050629793, SIAM J. Matrix Anal. Appl. 30 (2008), 731-740. (2008) MR2421468DOI10.1137/050629793
  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. (2012) Zbl1241.05076MR2917414
  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. (2013) MR3090441
  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. (2012) Zbl1252.05118MR2889573
  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]. MR3027310
  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. (2014) MR3141806
  11. Fallat, S., Hogben, L., The minimum rank of symmetric matrices described by a graph: a survey, Linear Algebra Appl. 426 (2007), 558-582. (2007) Zbl1122.05057MR2350678
  12. Nylen, P. M., Minimum-rank matrices with prescribed graph, Linear Algebra Appl. 248 (1996), 303-316. (1996) Zbl0864.05069MR1416462
  13. Owens, K., Properties of the Zero Forcing Number, Master's Thesis, Brigham Young University (2009). (2009) 
  14. Peters, T., Positive semidefinite maximum nullity and zero forcing number, Electron. J. Linear Algebra (electronic only) 23 (2012), 815-830. (2012) Zbl1252.05130MR2992396
  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. (2012) Zbl1241.05086MR2917419
  16. Yu, X., 10.1016/0012-365X(92)90150-E, Discrete Math. 105 (1992), 275-284. (1992) Zbl0783.05065MR1180211DOI10.1016/0012-365X(92)90150-E

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.