Zero forcing sets and the minimum rank of graphs
| Autor: | Rana Mikkelson, Sivaram K. Narayan, Dragoš Cvetković, Willem H. Haemers, Leslie Hogben, Olga Pryporova, Chris Godsil, Hein van der Holst, Sebastian M. Cioabă, Shaun M. Fallat, Francesco Barioli, Wasin So, Wayne Barrett, Kevin N. Vander Meulen, Amy Wangsness Wehe, Dragan Stevanović, Steve Butler, Irene Sciriha |
|---|---|
| Přispěvatelé: | Stochastic Operations Research, Combinatorial Optimization 1 |
| Jazyk: | angličtina |
| Rok vydání: | 2008 |
| Předmět: |
Computation
Symmetric matrix Circuit rank 010103 numerical & computational mathematics 0102 computer and information sciences Tree-depth 01 natural sciences Graph Combinatorics Matrix (mathematics) Discrete Mathematics and Combinatorics 0101 mathematics Mathematics Discrete mathematics Numerical Analysis Algebra and Number Theory Matrix Minimum rank of a graph Minimum rank Graph theory Rank 2 × 2 real matrices 010201 computation theory & mathematics Geometry and Topology MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Linear Algebra and Its Applications, 428(7), 1628-1648. Elsevier |
| ISSN: | 0024-3795 |
| DOI: | 10.1016/j.laa.2007.10.009 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect