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 条
[11]   Minimum-rank matrices with prescribed graph [J].
Nylen, PM .
LINEAR ALGEBRA AND ITS APPLICATIONS, 1996, 248 :303-316
[12]  
Owens K. D., 2009, THESIS
[13]  
Peters T, 2012, ELECTRON J LINEAR AL, V23, P815
[14]   A technique for computing the zero forcing number of a graph with a cut-vertex [J].
Row, Darren D. .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2012, 436 (12) :4423-4432
[15]   CYCLOMATIC NUMBERS OF CONNECTED INDUCED SUBGRAPHS [J].
YU, XX .
DISCRETE MATHEMATICS, 1992, 105 (1-3) :275-284
[16]  
2008, LINEAR ALGEBRA APPL, V428, P1628, DOI DOI 10.1016/J.LAA.2007.10.009