On the graph complement conjecture for minimum rank

DOI10.1016/J.LAA.2010.12.024MaRDI QIDQ417528zbMATHOpenAlexWikidataFDO

Authors Francesco Barioli, H. Tracy Hall, Leslie Hogben, Hein van der Holst, Shaun M. Fallat, Wayne 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

graph\(k\)-treesjoin of graphsminimum rankminimum semidefinite rankmaximum multiplicitygraph complementHadwiger numberNordhaus-Gaddum typeColin de Verdière type parameters

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)

Recommendations

• Bounds on the sum of minimum semidefinite rank of a graph and its complement
• Graph complement conjecture for classes of shadow graphs
• On the minimum rank of the join of graphs and decomposable graphs
• The minimum semidefinite rank of the complement of partial \(k\)-trees
• An upper bound for the minimum rank of a graph

Cites work

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

Cited in

(30)

• Bounds on the sum of minimum semidefinite rank of a graph and its complement
• Minimal comparability completions of arbitrary graphs
• Odd cycle zero forcing parameters and the minimum rank of graph blowups
• scientific article; zbMATH DE number 5059933 (Why is no real title available?)
• On the graph complement conjecture for minimum semidefinite rank
• Failed power domination on graphs
• Sphere representations, stacked polytopes, and the Colin de Verdière number of a graph
• On the minimum rank of a graph over finite fields
• A new lower bound for the positive semidefinite minimum rank of a graph
• The extremal function and Colin de Verdière graph parameter
• The Colin de Verdière number and joins of graphs
• Minimum vector rank and complement critical graphs
• On the enumeration of minimal non-pairwise compatibility graphs
• Bounds on the connected forcing number of a graph
• On the minimum rank of the join of graphs and decomposable graphs
• Determining the minimum rank of matroids whose basis graph is common
• Some relations between rank of a graph and its complement
• Computational and Theoretical Challenges for Computing the Minimum Rank of a Graph
• A Nordhaus-Gaddum conjecture for the minimum number of distinct eigenvalues of a graph
• On the minimum vector rank of multigraphs
• Graph complement conjecture for classes of shadow graphs
• Compositions constrained by graph Laplacian minors
• Minimal \(N_{+}\)-rank graphs: progress on Lipták and Tunçel's conjecture
• Positive semidefinite zero forcing
• Characterizing and Computing Minimal Cograph Completions
• On the minimum semidefinite rank of a simple graph
• Generalizations of the strong Arnold property and the minimum number of distinct eigenvalues of a graph
• Orthogonal representations, minimum rank, and graph complements
• Approximating the minimum rank of a graph via alternating projection
• On delta-graphs and delta conjecture

This page was built for publication: On the graph complement conjecture for minimum rank

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q417528)