TY - JOUR
T1 - On minimum rank and zero forcing sets of a graph
AU - Huang, Liang Hao
AU - Chang, Gerard J.
AU - Yeh, Hong Gwa
N1 - Funding Information:
E-mail addresses: [email protected] (L.-H. Huang), [email protected] (G.J. Chang), [email protected] (H.-G. Yeh). 1 Partially supported by National Science Council under Grant NSC98-2811-M-008-072. 2 Partially supported by National Science Council under Grant NSC98-2115-M-002-013-MY3. 3 Partially supported by National Science Council under Grant NSC97-2628-M-008-018-MY3.
PY - 2010/6/1
Y1 - 2010/6/1
N2 - For a graph G on n vertices and a field F, the minimum rank of G over F, written as mrF (G), is the smallest possible rank over all n × n symmetric matrices over F whose (i, j)th entry (for i ≠ j) is nonzero whenever ij is an edge in G and is zero otherwise. The maximum nullity of G over F is MF (G) = n - mrF (G). The minimum rank problem of a graph G is to determine mrF (G) (or equivalently, MF (G)). This problem has received considerable attention over the years. In [F. Barioli, W. Barrett, S. Butler, S.M. Cioabǎ, D. Cvetković, S.M. Fallat, C. Godsil, W. Haemers, L. Hogben, R. Mikkelson, S. Narayan, O. Pryporova, I. Sciriha, W. So, D. Stevanović, H. van der Holst, K.V. Meulen, A.W. Wehe, AIM Minimum Rank-Special Graphs Work Group, Zero forcing sets and the minimum rank of graphs, Linear Algebra Appl. 428 (2008) 1628-1648], a new graph parameter Z (G), the zero forcing number, was introduced to bound MF (G) from above. The authors posted an attractive question: What is the class of graphs G for which Z (G) = MF (G) for some field F? This paper focuses on exploring the above question.
AB - For a graph G on n vertices and a field F, the minimum rank of G over F, written as mrF (G), is the smallest possible rank over all n × n symmetric matrices over F whose (i, j)th entry (for i ≠ j) is nonzero whenever ij is an edge in G and is zero otherwise. The maximum nullity of G over F is MF (G) = n - mrF (G). The minimum rank problem of a graph G is to determine mrF (G) (or equivalently, MF (G)). This problem has received considerable attention over the years. In [F. Barioli, W. Barrett, S. Butler, S.M. Cioabǎ, D. Cvetković, S.M. Fallat, C. Godsil, W. Haemers, L. Hogben, R. Mikkelson, S. Narayan, O. Pryporova, I. Sciriha, W. So, D. Stevanović, H. van der Holst, K.V. Meulen, A.W. Wehe, AIM Minimum Rank-Special Graphs Work Group, Zero forcing sets and the minimum rank of graphs, Linear Algebra Appl. 428 (2008) 1628-1648], a new graph parameter Z (G), the zero forcing number, was introduced to bound MF (G) from above. The authors posted an attractive question: What is the class of graphs G for which Z (G) = MF (G) for some field F? This paper focuses on exploring the above question.
KW - Block-clique graph
KW - Maximum nullity
KW - Minimum rank
KW - Product graph
KW - Rank
KW - Symmetric matrix
KW - Unit interval graph
KW - Zero forcing set
UR - http://www.scopus.com/inward/record.url?scp=77949875255&partnerID=8YFLogxK
U2 - 10.1016/j.laa.2010.01.001
DO - 10.1016/j.laa.2010.01.001
M3 - 期刊論文
AN - SCOPUS:77949875255
SN - 0024-3795
VL - 432
SP - 2961
EP - 2973
JO - Linear Algebra and Its Applications
JF - Linear Algebra and Its Applications
IS - 11
ER -