On the graph complement conjecture for minimum rank

DOI10.1016/j.laa.2010.12.024zbMath1241.05064OpenAlexW2038330747WikidataQ123128544 ScholiaQ123128544MaRDI QIDQ417528

Leslie Hogben, H. Tracy Hall, Hein van der Holst, Francesco Barioli, Shaun M. Fallat, Wayne W. Barrett

Publication date: 14 May 2012

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

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

zbMATH Keywords

graphNordhaus-Gaddum typeminimum semidefinite rank\(k\)-treesminimum rankjoin of graphsmaximum multiplicityColin de Verdière type parametersgraph complementHadwiger number

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) Vector spaces, linear dependence, rank, lineability (15A03)

Related Items

Generalizations of the strong Arnold property and the minimum number of distinct eigenvalues of a graph ⋮ Computational and Theoretical Challenges for Computing the Minimum Rank of a Graph ⋮ Unnamed Item ⋮ A new lower bound for the positive semidefinite minimum rank of a graph ⋮ Sphere representations, stacked polytopes, and the Colin de Verdière number of a graph ⋮ Positive semidefinite zero forcing ⋮ A Nordhaus-Gaddum conjecture for the minimum number of distinct eigenvalues of a graph ⋮ The extremal function and Colin de Verdière graph parameter ⋮ Bounds on the connected forcing number of a graph ⋮ On the graph complement conjecture for minimum semidefinite rank ⋮ Failed power domination on graphs ⋮ The Colin de Verdière number and joins of graphs ⋮ Approximating the minimum rank of a graph via alternating projection ⋮ Odd Cycle Zero Forcing Parameters and the Minimum Rank of Graph Blowups ⋮ Graph complement conjecture for classes of shadow graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The minimum semidefinite rank of the complement of partial \(k\)-trees
• Lower bound of the Hadwiger number of graphs by their average degree
• Linearly independent vertices and minimum semidefinite rank
• On the minimum rank of the join of graphs and decomposable graphs
• Orthogonal representations, minimum rank, and graph complements
• Three-connected graphs whose maximum nullity is at most three
• Techniques for determining the minimum rank of a small graph
• The minimum rank of symmetric matrices described by a graph: a survey
• The Colin de Verdière number and sphere representations of a graph
• Graphs whose positive semi-definite matrices have nullity at most two
• Multiplicities of eigenvalues and tree-width of graphs
• A correction: Orthogonal representations and connectivity of graphs
• Orthogonal representations and connectivity of graphs
• Zero forcing sets and the minimum rank of graphs
• A characterization of tridiagonal matrices
• Graphs whose minimal rank is two
• A variant on the graph parameters of Colin de Verdiere: Implications to the minimum rank of graphs