Graphs with many valencies and few eigenvalues

zbMATH Open1320.05082arXiv1405.3383MaRDI QIDQ5502153FDOQ5502153

Authors: Edwin R. Van Dam, Zheng-Jiang Xia, Jack H. Koolen 

Publication date: 17 August 2015

Abstract: Dom de Caen posed the question whether connected graphs with three distinct eigenvalues have at most three distinct valencies. We do not answer this question, but instead construct connected graphs with four and five distinct eigenvalues and arbitrarily many distinct valencies. The graphs with four distinct eigenvalues come from regular two-graphs. As a side result, we characterize the disconnected graphs and the graphs with three distinct eigenvalues in the switching class of a regular two-graph.

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

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

Recommendations

• On regular graphs with four distinct eigenvalues
• Regular graphs with four eigenvalues
• Biregular graphs with three eigenvalues
• A note on graphs with exactly two main eigenvalues
• Graphs with three distinct eigenvalues and largest eigenvalue less than 8

zbMATH Keywords

eigenvalues of graphsSeidel switchingregular two-graphsstrong graphsnon-regular graphsfew eigenvalues

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Cited In (14)

• Open problems in the spectral theory of signed graphs
• Biregular graphs with three eigenvalues
• On 2-equitable graphs
• Graphs with few distinct eigenvalues and extremal energy
• Graphs with three eigenvalues and second largest eigenvalue at most 1
• On the multiplicity of the least signless Laplacian eigenvalue of a graph
• The graphs with all but two eigenvalues equal to \(-2\) or 0
• Characterization of graphs with some normalized Laplacian eigenvalue of multiplicity \(n - 3\)
• A note on graphs with exactly two main eigenvalues
• On regular graphs with four distinct eigenvalues
• Graphs with two main and two plain eigenvalues
• Graphs with given valences
• On the multiplicity of Laplacian eigenvalues for unicyclic graphs
• The characterization of graphs with eigenvalue -1 of multiplicity n-4 or n-5

This page was built for publication: Graphs with many valencies and few eigenvalues

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