Lower bounds for minimum semidefinite rank from orthogonal removal and chordal supergraphs

DOI10.1016/j.laa.2011.07.004zbMath1229.05204OpenAlexW2092845797MaRDI QIDQ649553

Lon H. Mitchell, Andrew M. Zimmer, Sivaram K. Narayan

Publication date: 2 December 2011

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.laa.2011.07.004

zbMATH Keywords

linearly independent verticesminimum semidefinite rank (msr)ordered subgraph number (OS number)orthogonal vertex removal

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Hermitian, skew-Hermitian, and related matrices (15B57)

Related Items (5)

On the minimum semidefinite rank of signed graphs ⋮ A new lower bound for the positive semidefinite minimum rank of a graph ⋮ A reduction procedure for the Colin de Verdière number of a graph ⋮ Positive semidefinite zero forcing numbers of two classes of graphs ⋮ Graph complement conjecture for classes of shadow graphs

Cites Work

• Vector representations of graphs
• Linearly independent vertices and minimum semidefinite rank
• Converse to the Parter--Wiener theorem: the case of non-trees
• Zero forcing parameters and minimum rank problems
• The minimum rank of symmetric matrices described by a graph: a survey
• Lower bounds in minimum rank problems
• Graphs whose positive semi-definite matrices have nullity at most two
• On the possible multiplicities of the eigenvalues of a Hermitian matrix whose graph is a tree
• Zero forcing sets and the minimum rank of graphs
• Unitary matrix digraphs and minimum semidefinite rank
• On the minimum semidefinite rank of a simple graph
• On the minimum vector rank of multigraphs
• Minimum semidefinite rank of outerplanar graphs and the tree cover number
• On the Minimum Rank Among Positive Semidefinite Matrices with a Given Graph
• Graphs whose minimal rank is two
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Lower bounds for minimum semidefinite rank from orthogonal removal and chordal supergraphs