Geodesic
Line graphs: their maximum nullities and zero forcing numbers
Czechoslovak Mathematical Journal, Tome 66 (2016) no. 3, pp. 743-755
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.1007/s10587-016-0290-x
Classification : 05C50, 15A03, 15A18
Keywords: maximum nullity; zero forcing number; positive zero forcing number; line graphs; matrix; tree; positive semidefinite matrix; unicyclic graph 
@article{10_1007_s10587_016_0290_x,
     author = {Fallat, Shaun and Soltani, Abolghasem},
     title = {Line graphs: their maximum nullities and zero forcing numbers},
     journal = {Czechoslovak Mathematical Journal},
     pages = {743--755},
     year = {2016},
     volume = {66},
     number = {3},
     doi = {10.1007/s10587-016-0290-x},
     mrnumber = {3556865},
     zbl = {06644031},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10587-016-0290-x/}
}
TY  - JOUR
AU  - Fallat, Shaun
AU  - Soltani, Abolghasem
TI  - Line graphs: their maximum nullities and zero forcing numbers
JO  - Czechoslovak Mathematical Journal
PY  - 2016
SP  - 743
EP  - 755
VL  - 66
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10587-016-0290-x/
DO  - 10.1007/s10587-016-0290-x
LA  - en
ID  - 10_1007_s10587_016_0290_x
ER  - 
%0 Journal Article
%A Fallat, Shaun
%A Soltani, Abolghasem
%T Line graphs: their maximum nullities and zero forcing numbers
%J Czechoslovak Mathematical Journal
%D 2016
%P 743-755
%V 66
%N 3
%U http://geodesic.mathdoc.fr/articles/10.1007/s10587-016-0290-x/
%R 10.1007/s10587-016-0290-x
%G en
%F 10_1007_s10587_016_0290_x
Fallat, Shaun; Soltani, Abolghasem. Line graphs: their maximum nullities and zero forcing numbers. Czechoslovak Mathematical Journal, Tome 66 (2016) no. 3, pp. 743-755. doi: 10.1007/s10587-016-0290-x

[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

[2] Alinaghipour, F.: Zero Forcing Set for Graphs. PhD Dissertation, University of Regina (2013). | MR

[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

[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 | Zbl

[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 | MR

[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 | Zbl

[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

[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 | Zbl

[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

[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

[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 | Zbl

[12] Nylen, P. M.: Minimum-rank matrices with prescribed graph. Linear Algebra Appl. 248 (1996), 303-316. | MR | Zbl

[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 | Zbl

[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 | Zbl

[16] Yu, X.: Cyclomatic numbers of connected induced subgraphs. Discrete Math. 105 (1992), 275-284. | DOI | MR | Zbl

Cité par Sources :