Zero forcing sets and the minimum rank of graphs

H. Holst, van der, F. Barioli, W. Barrett, S. Butler, S.M. Cioaba, D.M. Cvetkovic, S.M. Fallat, C.D. Godsil, W.H. Haemers, L. Hogben, R. Mikkelson, S. Narayan, O. Pryporova, I. Sciriha, W. So, D. Stevanovic, K.N. Vander Meulen, A. Wangsness Wehe

Research output: Contribution to journalArticleAcademicpeer-review

144 Citations (Scopus)
5 Downloads (Pure)

Abstract

The minimum rank of a simple graph G is defined to be the smallest possible rank over all symmetric real matrices whose ijth entry (for i¿j) is nonzero whenever {i,j} is an edge in G and is zero otherwise. This paper introduces a new graph parameter, Z(G), that is the minimum size of a zero forcing set of vertices and uses it to bound the minimum rank for numerous families of graphs, often enabling computation of the minimum rank.
Original languageEnglish
Pages (from-to)1628-1648
JournalLinear Algebra and Its Applications
Volume428
Issue number7
DOIs
Publication statusPublished - 2008

Fingerprint

Minimum Rank
Zero-forcing
Graph in graph theory
Simple Graph
Zero

Cite this

Holst, van der, H., Barioli, F., Barrett, W., Butler, S., Cioaba, S. M., Cvetkovic, D. M., ... Wangsness Wehe, A. (2008). Zero forcing sets and the minimum rank of graphs. Linear Algebra and Its Applications, 428(7), 1628-1648. https://doi.org/10.1016/j.laa.2007.10.009
Holst, van der, H. ; Barioli, F. ; Barrett, W. ; Butler, S. ; Cioaba, S.M. ; Cvetkovic, D.M. ; Fallat, S.M. ; Godsil, C.D. ; Haemers, W.H. ; Hogben, L. ; Mikkelson, R. ; Narayan, S. ; Pryporova, O. ; Sciriha, I. ; So, W. ; Stevanovic, D. ; Vander Meulen, K.N. ; Wangsness Wehe, A. / Zero forcing sets and the minimum rank of graphs. In: Linear Algebra and Its Applications. 2008 ; Vol. 428, No. 7. pp. 1628-1648.
@article{0ca77edb3529452884c5c71e467877b0,
title = "Zero forcing sets and the minimum rank of graphs",
abstract = "The minimum rank of a simple graph G is defined to be the smallest possible rank over all symmetric real matrices whose ijth entry (for i¿j) is nonzero whenever {i,j} is an edge in G and is zero otherwise. This paper introduces a new graph parameter, Z(G), that is the minimum size of a zero forcing set of vertices and uses it to bound the minimum rank for numerous families of graphs, often enabling computation of the minimum rank.",
author = "{Holst, van der}, H. and F. Barioli and W. Barrett and S. Butler and S.M. Cioaba and D.M. Cvetkovic and S.M. Fallat and C.D. Godsil and W.H. Haemers and L. Hogben and R. Mikkelson and S. Narayan and O. Pryporova and I. Sciriha and W. So and D. Stevanovic and {Vander Meulen}, K.N. and {Wangsness Wehe}, A.",
year = "2008",
doi = "10.1016/j.laa.2007.10.009",
language = "English",
volume = "428",
pages = "1628--1648",
journal = "Linear Algebra and Its Applications",
issn = "0024-3795",
publisher = "Elsevier",
number = "7",

}

Holst, van der, H, Barioli, F, Barrett, W, Butler, S, Cioaba, SM, Cvetkovic, DM, Fallat, SM, Godsil, CD, Haemers, WH, Hogben, L, Mikkelson, R, Narayan, S, Pryporova, O, Sciriha, I, So, W, Stevanovic, D, Vander Meulen, KN & Wangsness Wehe, A 2008, 'Zero forcing sets and the minimum rank of graphs', Linear Algebra and Its Applications, vol. 428, no. 7, pp. 1628-1648. https://doi.org/10.1016/j.laa.2007.10.009

Zero forcing sets and the minimum rank of graphs. / Holst, van der, H.; Barioli, F.; Barrett, W.; Butler, S.; Cioaba, S.M.; Cvetkovic, D.M.; Fallat, S.M.; Godsil, C.D.; Haemers, W.H.; Hogben, L.; Mikkelson, R.; Narayan, S.; Pryporova, O.; Sciriha, I.; So, W.; Stevanovic, D.; Vander Meulen, K.N.; Wangsness Wehe, A.

In: Linear Algebra and Its Applications, Vol. 428, No. 7, 2008, p. 1628-1648.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Zero forcing sets and the minimum rank of graphs

AU - Holst, van der, H.

AU - Barioli, F.

AU - Barrett, W.

AU - Butler, S.

AU - Cioaba, S.M.

AU - Cvetkovic, D.M.

AU - Fallat, S.M.

AU - Godsil, C.D.

AU - Haemers, W.H.

AU - Hogben, L.

AU - Mikkelson, R.

AU - Narayan, S.

AU - Pryporova, O.

AU - Sciriha, I.

AU - So, W.

AU - Stevanovic, D.

AU - Vander Meulen, K.N.

AU - Wangsness Wehe, A.

PY - 2008

Y1 - 2008

N2 - The minimum rank of a simple graph G is defined to be the smallest possible rank over all symmetric real matrices whose ijth entry (for i¿j) is nonzero whenever {i,j} is an edge in G and is zero otherwise. This paper introduces a new graph parameter, Z(G), that is the minimum size of a zero forcing set of vertices and uses it to bound the minimum rank for numerous families of graphs, often enabling computation of the minimum rank.

AB - The minimum rank of a simple graph G is defined to be the smallest possible rank over all symmetric real matrices whose ijth entry (for i¿j) is nonzero whenever {i,j} is an edge in G and is zero otherwise. This paper introduces a new graph parameter, Z(G), that is the minimum size of a zero forcing set of vertices and uses it to bound the minimum rank for numerous families of graphs, often enabling computation of the minimum rank.

U2 - 10.1016/j.laa.2007.10.009

DO - 10.1016/j.laa.2007.10.009

M3 - Article

VL - 428

SP - 1628

EP - 1648

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

SN - 0024-3795

IS - 7

ER -

Holst, van der H, Barioli F, Barrett W, Butler S, Cioaba SM, Cvetkovic DM et al. Zero forcing sets and the minimum rank of graphs. Linear Algebra and Its Applications. 2008;428(7):1628-1648. https://doi.org/10.1016/j.laa.2007.10.009