Graphs with many valencies and few eigenvalues

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

Research output: Contribution to journalArticleScientificpeer-review

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

Fingerprint

Eigenvalue
Distinct
Graph in graph theory
Connected graph

Keywords

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

Cite this

van Dam, Edwin ; Koolen, J.H. ; Xia, Zheng-Jiang. / Graphs with many valencies and few eigenvalues. In: Electronic Journal of Linear Algebra. 2015 ; Vol. 28. pp. 12-24.
@article{e99aab0d85cc4405a668f729c9ccdb4a,
title = "Graphs with many valencies and few eigenvalues",
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.",
keywords = "Eigenvalues of graphs, non-regular graphs, few eigenvalues, strong graphs, regular two-graphs, Seidel switching",
author = "{van Dam}, Edwin and J.H. Koolen and Zheng-Jiang Xia",
year = "2015",
month = "4",
doi = "10.13001/1081-3810.2987",
language = "English",
volume = "28",
pages = "12--24",
journal = "Electronic Journal of Linear Algebra",
issn = "1081-3810",
publisher = "International Linear Algebra Society",

}

Graphs with many valencies and few eigenvalues. / van Dam, Edwin; Koolen, J.H.; Xia, Zheng-Jiang.

In: Electronic Journal of Linear Algebra, Vol. 28, 3, 04.2015, p. 12-24.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Graphs with many valencies and few eigenvalues

AU - van Dam, Edwin

AU - Koolen, J.H.

AU - Xia, Zheng-Jiang

PY - 2015/4

Y1 - 2015/4

N2 - 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.

AB - 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.

KW - Eigenvalues of graphs

KW - non-regular graphs

KW - few eigenvalues

KW - strong graphs

KW - regular two-graphs

KW - Seidel switching

U2 - 10.13001/1081-3810.2987

DO - 10.13001/1081-3810.2987

M3 - Article

VL - 28

SP - 12

EP - 24

JO - Electronic Journal of Linear Algebra

JF - Electronic Journal of Linear Algebra

SN - 1081-3810

M1 - 3

ER -