Graphs with many valencies and few eigenvalues

Edwin van Dam, J.H. Koolen, Zheng-Jiang Xia

Research output: Contribution to journalArticleScientificpeer-review

11 Citations (Scopus)

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.
Original languageEnglish
Article number3
Pages (from-to)12-24
JournalElectronic Journal of Linear Algebra
Volume28
DOIs
Publication statusPublished - Apr 2015

Keywords

  • Eigenvalues of graphs
  • non-regular graphs
  • few eigenvalues
  • strong graphs
  • regular two-graphs
  • Seidel switching

Fingerprint Dive into the research topics of 'Graphs with many valencies and few eigenvalues'. Together they form a unique fingerprint.

  • Cite this