Line graphs: Their maximum nullities and zero forcing numbers

被引:6
作者
Fallat, Shaun [1 ]
Soltani, Abolchasem [2 ]
机构
[1] Univ Regina, Dept Math & Stat, 3737 Wascana Parkway, Regina, SK S4S 0A4, Canada
[2] Tarbiat Modares Univ, Fac Math Sci, Dept Pure Math, Jalal AleAhmad Nasr 7, Tehran 14115134, Iran
基金
加拿大自然科学与工程研究理事会;
关键词
MINIMUM-RANK; MATRICES;
D O I
10.1007/s10587-016-0290-x
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
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.
引用
收藏
页码:743 / 755
页数:13
相关论文
共 16 条
[1]  
Alinaghipour F, 2013, THESIS
[2]   On the difference between the maximum multiplicity and path cover number for tree-like graphs [J].
Barioli, F ;
Fallat, S ;
Hogben, L .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2005, 409 :13-31
[3]   Zero forcing parameters and minimum rank problems [J].
Barioli, Francesco ;
Barrett, Wayne ;
Fallat, Shaun M. ;
Hall, H. Tracy ;
Hogben, Leslie ;
Shader, Bryan ;
van den Driessche, P. ;
van der Holst, Hein .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2010, 433 (02) :401-411
[4]   ON THE MINIMUM RANK AMONG POSITIVE SEMIDEFINITE MATRICES WITH A GIVEN GRAPH [J].
Booth, Matthew ;
Hackney, Philip ;
Harris, Benjamin ;
Johnson, Charles R. ;
Lay, Margaret ;
Mitchell, Lon H. ;
Narayan, Sivaram K. ;
Pascoe, Amanda ;
Steinmetz, Kelly ;
Sutton, Brian D. ;
Wang, Wendy .
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 2008, 30 (02) :731-740
[5]   Vertex and edge spread of zero forcing number, maximum nullity, and minimum rank of a graph [J].
Edholm, Christina J. ;
Hogben, Leslie ;
My Huynh ;
LaGrange, Joshua ;
Row, Darren D. .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2012, 436 (12) :4352-4372
[6]  
Ekstrand J, 2012, ELECTRON J LINEAR AL, V23, P79
[7]   Positive semidefinite zero forcing [J].
Ekstrand, Jason ;
Erickson, Craig ;
Hall, H. Tracy ;
Hay, Diana ;
Hogben, Leslie ;
Johnson, Ryan ;
Kingsley, Nicole ;
Osborne, Steven ;
Peters, Travis ;
Roat, Jolie ;
Ross, Arianne ;
Row, Darren D. ;
Warnberg, Nathan ;
Young, Michael .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2013, 439 (07) :1862-1874
[8]  
Eroh L, 2012, ARXIV12076127V1MATHC
[9]  
Fallat S. M., 2014, HDB LINEAR ALGEBRA
[10]   The minimum rank of symmetric matrices described by a graph: A survey [J].
Fallat, Shaun M. ;
Hogben, Leslie .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2007, 426 (2-3) :558-582