Minimum number of distinct eigenvalues of graphs

DOI10.13001/1081-3810.1679MaRDI QIDQ5746835zbMATH OpenOpenAlexFDO

Authors Shaun M. Fallat, K. Meagher, Shahla Nasser, B. Ahmadi, F. Alinaghipour, M. Cavers

Publication date 10 February 2014

Published in The Electronic Journal of Linear Algebra (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.1205, http://www.math.technion.ac.il/iic/ela/ela-articles/articles/vol26_pp673-691.pdf

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

bipartite graphdiametereigenvaluejoin of graphsmaximum multiplicitysymmetric matrix

Mathematics Subject Classification ID

Trees (05C05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18)

Abstract: The minimum number of distinct eigenvalues, taken over all real symmetric matrices compatible with a given graph $G$, is denoted by $q(G)$. Using other parameters related to $G$, bounds for $q(G)$ are proven and then applied to deduce further properties of $q(G)$. It is shown that there is a great number of graphs $G$ for which $q(G)=2$. For some families of graphs, such as the join of a graph with itself, complete bipartite graphs, and cycles, this minimum value is obtained. Moreover, examples of graphs $G$ are provided to show that adding and deleting edges or vertices can dramatically change the value of $q(G)$. Finally, the set of graphs $G$ with $q(G)$ near the number of vertices is shown to be a subset of known families of graphs with small maximum multiplicity.

Recommendations

• On the minimum number of distinct eigenvalues of a threshold graph
• A Nordhaus-Gaddum conjecture for the minimum number of distinct eigenvalues of a graph
• Applications of analysis to the determination of the minimum number of distinct eigenvalues of a graph
• On graphs with distinct eigenvalues
• The least eigenvalue of graphs
• Graphs with few distinct eigenvalues and extremal energy
• Eigenvalues and parity factors in graphs with given minimum degree
• Graphs with few distinct \(D\)-eigenvalues determined by their \(D\)-spectra
• scientific article; zbMATH DE number 500503
• On the minimum number of distinct eigenvalues for a symmetric matrix whose graph is a given tree

Cited in

(40)

• A Nordhaus-Gaddum conjecture for the minimum number of distinct eigenvalues of a graph
• A zero forcing technique for bounding sums of eigenvalue multiplicities
• The inverse eigenvalue problem of a graph: multiplicities and minors
• Sign patterns of orthogonal matrices and the strong inner product property
• Rigid linkages and partial zero forcing
• Graphs with few distinct eigenvalues and extremal energy
• Minimum number of distinct eigenvalues allowed by a sign pattern
• A theorem on the number of distinct eigenvalues
• On the minimum number of distinct eigenvalues of a threshold graph
• Orthogonal symmetric matrices and joins of graphs
• The strong spectral property for graphs
• On the minimum number of distinct eigenvalues in the problem for a tree formed by Stieltjes strings
• Corrigendum to: ``Achievable multiplicity partitions in the inverse eigenvalue problem of a graph
• On the inverse eigenvalue problem for block graphs
• Achievable multiplicity partitions in the inverse eigenvalue problem of a graph
• Generalizations of the strong Arnold property and the minimum number of distinct eigenvalues of a graph
• Graphs that allow all the eigenvalue multiplicities to be even
• The nowhere-zero eigenbasis problem for a graph
• A lower bound for the number of distinct eigenvalues of some real symmetric matrices
• The maximum of the minimal multiplicity of eigenvalues of symmetric matrices whose pattern is constrained by a graph
• Frame graph
• Tight frame graphs arising as line graphs
• scientific article; zbMATH DE number 7640506 (Why is no real title available?)
• scientific article; zbMATH DE number 7559433 (Why is no real title available?)
• Applications of analysis to the determination of the minimum number of distinct eigenvalues of a graph
• On orthogonal matrices with zero diagonal
• An explicit upper bound on disparity for trees of a given diameter
• 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
• Sparsity of graphs that allow two distinct eigenvalues
• Diminimal families of arbitrary diameter
• The allow sequence of distinct eigenvalues for a sign pattern
• Distinct eigenvalues are realizable with generic eigenvectors
• Graphs with bipartite complement that admit two distinct eigenvalues
• Graph products that allow two distinct eigenvalues
• A combinatorial bound on the number of distinct eigenvalues of a graph
• The minimum number of distinct eigenvalues of a threshold graph is at most 4
• Orthogonalisability of joins of graphs
• Sensitivity conjecture and signed hypercubes

This page was built for publication: Minimum number of distinct eigenvalues of graphs

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