A Nordhaus-Gaddum conjecture for the minimum number of distinct eigenvalues of a graph

DOI10.1016/j.laa.2018.12.001zbMath1405.05103arXiv1807.06436OpenAlexW2964121290WikidataQ122897758 ScholiaQ122897758MaRDI QIDQ1715848

Polona Oblak, Helena Šmigoc, Rupert H. Levene

Publication date: 29 January 2019

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

Full work available at URL: https://arxiv.org/abs/1807.06436

zbMATH Keywords

orthogonal matricesminimum rankinverse eigenvalue problem for graphsminimum number of distinct eigenvaluesNordhaus-Gaddum inequality

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) Orthogonal matrices (15B10)

Related Items

On the minimum number of distinct eigenvalues of a threshold graph, Orthogonal symmetric matrices and joins of graphs, The strong spectral property for graphs, Bordering of symmetric matrices and an application to the minimum number of distinct eigenvalues for the join of graphs, Regular graphs of degree at most four that allow two distinct eigenvalues, The strong spectral property of graphs: graph operations and barbell partitions, Corrigendum to: ``Achievable multiplicity partitions in the inverse eigenvalue problem of a graph, Achievable multiplicity partitions in the inverse eigenvalue problem of a graph, A theorem on the number of distinct eigenvalues

Cites Work

• Unnamed Item
• Unnamed Item
• The nowhere-zero eigenbasis problem for a graph
• On the graph complement conjecture for minimum rank
• The inverse eigenvalue problem for nonnegative matrices
• The minimum rank of symmetric matrices described by a graph: a survey
• A survey of Nordhaus-Gaddum type relations
• The inverse eigenvalue problem of a graph: multiplicities and minors
• Generalizations of the strong Arnold property and the minimum number of distinct eigenvalues of a graph
• A note on the domination number of a graph and its complement
• Nordhaus-Gaddum problems for Colin de Verdière type parameters, variants of tree-width, and related parameters
• A lower bound for the number of distinct eigenvalues of some real symmetric matrices
• On Complementary Graphs
• The maximum multiplicity of an eigenvalue in a matrix whose graph is a tree
• On the minimum number of distinct eigenvalues for a symmetric matrix whose graph is a given tree
• Ordered multiplicity inverse eigenvalue problem for graphs on six vertices
• Applications of analysis to the determination of the minimum number of distinct eigenvalues of a graph
• Minimum Vector Rank and Complement Critical Graphs
• Minimum number of distinct eigenvalues of graphs