Zero forcing sets and minimum rank of graphs

Francesco  Barioli; Wayne  Barrett; Steve Butler; S.M. Cioabǎ; D. Cvetković; Shaun M.  Fallat; Chris D.  Godsil; W.H. Haemers; Leslie  Hogben; Rana  Mikkelson; Sivaram K.  Narayan; Olga  Pryporova; Irene  Sciriha; Wasin  So; Dragan  Stevanovic; Hein  van der Holst; Kevin  Vander Meulen; Amy  Wangsness Wehe

Zero forcing sets and minimum rank of graphs

Francesco Barioli
, Wayne Barrett
, Steve Butler
, S.M. Cioabǎ
, D. Cvetković
, Shaun M. Fallat
, Chris D. Godsil
, W.H. Haemers
, Leslie Hogben
, Rana Mikkelson
, Sivaram K. Narayan
, Olga Pryporova
, Irene Sciriha
, Wasin So
, Dragan Stevanovic
, Hein van der Holst
, Kevin Vander Meulen
, Amy Wangsness Wehe

Econometrics and OR

Research output: Contribution to journal › Article › Scientific › peer-review

321 Citations (Scopus)

166 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 language	English
Pages (from-to)	1628-1648
Journal	Linear Algebra and its Applications
Volume	428
Issue number	7
Publication status	Published - 2008

Keywords

minimum rank
rank
graph
symmetric matrix
matrix

Access to Document

1-s2.0-S0024379507004624-mainFinal published version, 236 KB

Cite this

Barioli, F., Barrett, W., Butler, S., Cioabǎ, S. M., Cvetković, D., Fallat, S. M., Godsil, C. D., Haemers, W. H., Hogben, L., Mikkelson, R., Narayan, S. K., Pryporova, O., Sciriha, I., So, W., Stevanovic, D., van der Holst, H., Vander Meulen, K., & Wangsness Wehe, A. (2008). Zero forcing sets and minimum rank of graphs. Linear Algebra and its Applications, 428(7), 1628-1648.

@article{27e75224931249a4964bcb48fb614d87,

title = "Zero forcing sets and 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.",

keywords = "minimum rank, rank, graph, symmetric matrix, matrix",

author = "Francesco Barioli and Wayne Barrett and Steve Butler and S.M. Cioabǎ and D. Cvetkovi{\'c} and Fallat, \{Shaun M.\} and Godsil, \{Chris D.\} and W.H. Haemers and Leslie Hogben and Rana Mikkelson and Narayan, \{Sivaram K.\} and Olga Pryporova and Irene Sciriha and Wasin So and Dragan Stevanovic and \{van der Holst\}, Hein and \{Vander Meulen\}, Kevin and \{Wangsness Wehe\}, Amy",

year = "2008",

language = "English",

volume = "428",

pages = "1628--1648",

journal = "Linear Algebra and its Applications",

issn = "0024-3795",

publisher = "Elsevier Inc.",

number = "7",

}

TY - JOUR

T1 - Zero forcing sets and minimum rank of graphs

AU - Barioli, Francesco

AU - Barrett, Wayne

AU - Butler, Steve

AU - Cioabǎ, S.M.

AU - Cvetković, D.

AU - Fallat, Shaun M.

AU - Godsil, Chris D.

AU - Haemers, W.H.

AU - Hogben, Leslie

AU - Mikkelson, Rana

AU - Narayan, Sivaram K.

AU - Pryporova, Olga

AU - Sciriha, Irene

AU - So, Wasin

AU - Stevanovic, Dragan

AU - van der Holst, Hein

AU - Vander Meulen, Kevin

AU - Wangsness Wehe, Amy

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.

KW - minimum rank

KW - rank

KW - graph

KW - symmetric matrix

KW - matrix

M3 - Article

SN - 0024-3795

VL - 428

SP - 1628

EP - 1648

JO - Linear Algebra and its Applications

JF - Linear Algebra and its Applications

IS - 7

ER -

Zero forcing sets and minimum rank of graphs

Abstract

Keywords

Access to Document

Fingerprint

Cite this