Forbidden minors for the class of graphs G with $\xi (G) \leq 2$

L. Hogben, H. Holst, van der

Research output: Contribution to journalArticleAcademicpeer-review

17 Citations (Scopus)
2 Downloads (Pure)

Abstract

For a given simple graph G, is defined to be the set of real symmetric matrices A whose (i,j)th entry is nonzero whenever i¿j and ij is an edge in G. In [F. Barioli, S. Fallat, L. Hogben, A variant on the graph parameters of Colin de Verdière: Implications to the minimum rank of graphs, Electron. J. Linear Algebra 13 (2005) 387–404.], ¿(G) is defined to be the maximum corank (i.e., nullity) among having the Strong Arnold Property; ¿ is used to study the minimum rank/maximum eigenvalue multiplicity problem for G. Since ¿ is minor monotone, the graphs G such that ¿(G)k can be described by a finite set of forbidden minors. We determine the forbidden minors for ¿(G)2 and present an application of this characterization to computation of minimum rank among matrices in .
Original languageEnglish
Pages (from-to)42-52
JournalLinear Algebra and Its Applications
Volume423
Issue number1
DOIs
Publication statusPublished - 2007

Fingerprint

Forbidden Minor
Minimum Rank
Linear algebra
Graph in graph theory
Nullity
Simple Graph
Symmetric matrix
Electrons
Finite Set
Minor
Monotone
Multiplicity
Electron
Eigenvalue
Class

Cite this

Hogben, L. ; Holst, van der, H. / Forbidden minors for the class of graphs G with $\xi (G) \leq 2$. In: Linear Algebra and Its Applications. 2007 ; Vol. 423, No. 1. pp. 42-52.
@article{4f0c67efe4284b639e3d284d9515daa5,
title = "Forbidden minors for the class of graphs G with $\xi (G) \leq 2$",
abstract = "For a given simple graph G, is defined to be the set of real symmetric matrices A whose (i,j)th entry is nonzero whenever i¿j and ij is an edge in G. In [F. Barioli, S. Fallat, L. Hogben, A variant on the graph parameters of Colin de Verdi{\`e}re: Implications to the minimum rank of graphs, Electron. J. Linear Algebra 13 (2005) 387–404.], ¿(G) is defined to be the maximum corank (i.e., nullity) among having the Strong Arnold Property; ¿ is used to study the minimum rank/maximum eigenvalue multiplicity problem for G. Since ¿ is minor monotone, the graphs G such that ¿(G)k can be described by a finite set of forbidden minors. We determine the forbidden minors for ¿(G)2 and present an application of this characterization to computation of minimum rank among matrices in .",
author = "L. Hogben and {Holst, van der}, H.",
year = "2007",
doi = "10.1016/j.laa.2006.08.003",
language = "English",
volume = "423",
pages = "42--52",
journal = "Linear Algebra and Its Applications",
issn = "0024-3795",
publisher = "Elsevier",
number = "1",

}

Forbidden minors for the class of graphs G with $\xi (G) \leq 2$. / Hogben, L.; Holst, van der, H.

In: Linear Algebra and Its Applications, Vol. 423, No. 1, 2007, p. 42-52.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Forbidden minors for the class of graphs G with $\xi (G) \leq 2$

AU - Hogben, L.

AU - Holst, van der, H.

PY - 2007

Y1 - 2007

N2 - For a given simple graph G, is defined to be the set of real symmetric matrices A whose (i,j)th entry is nonzero whenever i¿j and ij is an edge in G. In [F. Barioli, S. Fallat, L. Hogben, A variant on the graph parameters of Colin de Verdière: Implications to the minimum rank of graphs, Electron. J. Linear Algebra 13 (2005) 387–404.], ¿(G) is defined to be the maximum corank (i.e., nullity) among having the Strong Arnold Property; ¿ is used to study the minimum rank/maximum eigenvalue multiplicity problem for G. Since ¿ is minor monotone, the graphs G such that ¿(G)k can be described by a finite set of forbidden minors. We determine the forbidden minors for ¿(G)2 and present an application of this characterization to computation of minimum rank among matrices in .

AB - For a given simple graph G, is defined to be the set of real symmetric matrices A whose (i,j)th entry is nonzero whenever i¿j and ij is an edge in G. In [F. Barioli, S. Fallat, L. Hogben, A variant on the graph parameters of Colin de Verdière: Implications to the minimum rank of graphs, Electron. J. Linear Algebra 13 (2005) 387–404.], ¿(G) is defined to be the maximum corank (i.e., nullity) among having the Strong Arnold Property; ¿ is used to study the minimum rank/maximum eigenvalue multiplicity problem for G. Since ¿ is minor monotone, the graphs G such that ¿(G)k can be described by a finite set of forbidden minors. We determine the forbidden minors for ¿(G)2 and present an application of this characterization to computation of minimum rank among matrices in .

U2 - 10.1016/j.laa.2006.08.003

DO - 10.1016/j.laa.2006.08.003

M3 - Article

VL - 423

SP - 42

EP - 52

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

SN - 0024-3795

IS - 1

ER -