On the graph complement conjecture for minimum rank

DOI10.1016/J.LAA.2010.12.024zbMATH Open1241.05064OpenAlexW2038330747WikidataQ123128544 ScholiaQ123128544MaRDI QIDQ417528FDOQ417528

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

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

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)

Cites Work

• Zero forcing sets and the minimum rank of graphs
• Lower bound of the Hadwiger number of graphs by their average degree
• The Colin de Verdière number and sphere representations of a graph
• Multiplicities of eigenvalues and tree-width of graphs
• Title not available (Why is that?)
• A variant on the graph parameters of Colin de Verdiere: Implications to the minimum rank of graphs
• Techniques for determining the minimum rank of a small graph
• Graphs whose positive semi-definite matrices have nullity at most two
• The minimum rank of symmetric matrices described by a graph: a survey
• Graphs whose minimal rank is two
• Orthogonal representations and connectivity of graphs
• A characterization of tridiagonal matrices
• Title not available (Why is that?)
• Linearly independent vertices and minimum semidefinite rank
• A correction: Orthogonal representations and connectivity of graphs
• Title not available (Why is that?)
• The minimum semidefinite rank of the complement of partial \(k\)-trees
• 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

Cited In (30)

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

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)