On minimum rank and zero forcing sets of a graph

Liang Hao Huang, Gerard J. Chang, Hong Gwa Yeh

Research output: Contribution to journalArticlepeer-review

40 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)2961-2973
Number of pages13
JournalLinear Algebra and Its Applications
Volume432
Issue number11
DOIs
StatePublished - 1 Jun 2010

Keywords

  • Block-clique graph
  • Maximum nullity
  • Minimum rank
  • Product graph
  • Rank
  • Symmetric matrix
  • Unit interval graph
  • Zero forcing set

Fingerprint

Dive into the research topics of 'On minimum rank and zero forcing sets of a graph'. Together they form a unique fingerprint.

Cite this