Regular graphs of degree at most four that allow two distinct eigenvalues

DOI10.1016/J.LAA.2023.09.012MaRDI QIDQ6084879zbMATH OpenFDO

Authors Wayne Barrett, Shaun M. Fallat, Veronika Furst, S. Nasserasr, Brendan Rooney, Michael Tait

Publication date 6 November 2023

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

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

zbMATH Keywords

\(q\)-parameterinverse eigenvalue problem for graphsorthogonalityregular graphs

Mathematics Subject Classification ID

Vertex degrees (05C07) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Inverse problems in linear algebra (15A29)

Abstract: For an $nimesn$ matrix $A$, let $q(A)$ be the number of distinct eigenvalues of $A$. If $G$ is a connected graph on $n$ vertices, let $mathcalS(G)$ be the set of all real symmetric $nimesn$ matrices $A=[a_{ij}]$ such that for $ieqj$, $a_{ij}=0$ if and only if $i,j$ is not an edge of $G$. Let $q(G)=mminq(A),:,AinmathcalS(G)$. Studying $q(G)$ has become a fundamental sub-problem of the inverse eigenvalue problem for graphs, and characterizing the case for which $q(G)=2$ has been especially difficult. This paper considers the problem of determining the regular graphs $G$ that satisfy $q(G)=2$. The resolution is straightforward if the degree of regularity is $1,2,$ or $3$. However, the $4$-regular graphs with $q(G)=2$ are much more difficult to characterize. A connected $4$-regular graph has $q(G)=2$ if and only if either $G$ belongs to a specific infinite class of graphs, or else $G$ is one of fifteen $4$-regular graphs whose number of vertices ranges from $5$ to $16$. This technical result gives rise to several intriguing questions.

Recommendations

• On regular graphs with four distinct eigenvalues
• Regular graphs with four eigenvalues
• Sparsity of graphs that allow two distinct eigenvalues
• Characterization of graphs with an eigenvalue of large multiplicity
• Graphs with four distinct Laplacian eigenvalues

Cites work

• A Nordhaus-Gaddum conjecture for the minimum number of distinct eigenvalues of a graph
• Achievable multiplicity partitions in the inverse eigenvalue problem of a graph
• Applications of analysis to the determination of the minimum number of distinct eigenvalues of a graph
• Cyclotomic matrices and graphs over the ring of integers of some imaginary quadratic fields
• Cyclotomic matrices over real quadratic integer rings
• Cyclotomic matrices over the Eisenstein and Gaussian integers
• Generalizations of the strong Arnold property and the minimum number of distinct eigenvalues of a graph
• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 43547 (Why is no real title available?)
• Integer symmetric matrices having all their eigenvalues in the interval \([ - 2,2]\)
• Inverse Problems and Zero Forcing for Graphs
• Minimum number of distinct eigenvalues of graphs
• On orthogonal matrices with zero diagonal
• 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
• Orthogonal symmetric matrices and joins of graphs
• Practical graph isomorphism. II.
• Sparsity of graphs that allow two distinct eigenvalues
• The inverse eigenvalue problem of a graph: multiplicities and minors
• Tight frame graphs arising as line graphs

Cited in

(6)

• Characterization of split graphs with at most four distinct eigenvalues
• On regular graphs with four distinct eigenvalues
• Graphs with bipartite complement that admit two distinct eigenvalues
• Graph products that allow two distinct eigenvalues
• The minimum number of distinct eigenvalues of a threshold graph is at most 4
• Orthogonalisability of joins of graphs

This page was built for publication: Regular graphs of degree at most four that allow two distinct eigenvalues

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