The graphs with all but two eigenvalues equal to - 2 or 0

Sebastian M. Cioabă, Willem H. Haemers, Jason R. Vermette

Research output: Contribution to journalArticleScientificpeer-review

Abstract

We determine all graphs whose adjacency matrix has at most two eigenvalues (multiplicities included) different from $\pm 1$ and decide which of these graphs are determined by their spectrum. This includes the so-called friendship graphs, which consist of a number of edge-disjoint triangles meeting in one vertex. It turns out that the friendship graph is determined by its spectrum, except when the number of triangles equals sixteen.
Original languageEnglish
Pages (from-to)153-163
JournalDesigns, Codes and Cryptography
Volume84
Issue number1-2
DOIs
Publication statusPublished - 1 Jul 2017

Fingerprint

Eigenvalue
Graph in graph theory
Triangle
p.m.
Adjacency Matrix
Multiplicity
Disjoint
Vertex of a graph

Keywords

  • Adjacency matrix
  • Graph spectrum
  • Spectral characterizations

Cite this

Cioabă, Sebastian M. ; Haemers, Willem H. ; Vermette, Jason R. / The graphs with all but two eigenvalues equal to - 2 or 0. In: Designs, Codes and Cryptography. 2017 ; Vol. 84, No. 1-2. pp. 153-163.
@article{5d680105d895443fbf726c94b176f901,
title = "The graphs with all but two eigenvalues equal to - 2 or 0",
abstract = "We determine all graphs whose adjacency matrix has at most two eigenvalues (multiplicities included) different from $\pm 1$ and decide which of these graphs are determined by their spectrum. This includes the so-called friendship graphs, which consist of a number of edge-disjoint triangles meeting in one vertex. It turns out that the friendship graph is determined by its spectrum, except when the number of triangles equals sixteen.",
keywords = "Adjacency matrix, Graph spectrum, Spectral characterizations",
author = "Cioabă, {Sebastian M.} and Haemers, {Willem H.} and Vermette, {Jason R.}",
year = "2017",
month = "7",
day = "1",
doi = "10.1007/s10623-016-0241-4",
language = "English",
volume = "84",
pages = "153--163",
journal = "Designs, Codes and Cryptography",
issn = "0925-1022",
publisher = "Springer Netherlands",
number = "1-2",

}

The graphs with all but two eigenvalues equal to - 2 or 0. / Cioabă, Sebastian M.; Haemers, Willem H.; Vermette, Jason R.

In: Designs, Codes and Cryptography, Vol. 84, No. 1-2, 01.07.2017, p. 153-163.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - The graphs with all but two eigenvalues equal to - 2 or 0

AU - Cioabă, Sebastian M.

AU - Haemers, Willem H.

AU - Vermette, Jason R.

PY - 2017/7/1

Y1 - 2017/7/1

N2 - We determine all graphs whose adjacency matrix has at most two eigenvalues (multiplicities included) different from $\pm 1$ and decide which of these graphs are determined by their spectrum. This includes the so-called friendship graphs, which consist of a number of edge-disjoint triangles meeting in one vertex. It turns out that the friendship graph is determined by its spectrum, except when the number of triangles equals sixteen.

AB - We determine all graphs whose adjacency matrix has at most two eigenvalues (multiplicities included) different from $\pm 1$ and decide which of these graphs are determined by their spectrum. This includes the so-called friendship graphs, which consist of a number of edge-disjoint triangles meeting in one vertex. It turns out that the friendship graph is determined by its spectrum, except when the number of triangles equals sixteen.

KW - Adjacency matrix

KW - Graph spectrum

KW - Spectral characterizations

U2 - 10.1007/s10623-016-0241-4

DO - 10.1007/s10623-016-0241-4

M3 - Article

VL - 84

SP - 153

EP - 163

JO - Designs, Codes and Cryptography

JF - Designs, Codes and Cryptography

SN - 0925-1022

IS - 1-2

ER -