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

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

doi:10.1007/s10623-016-0241-4

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

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

Econometrics and OR

Research output: Contribution to journal › Article › Scientific › peer-review

19 Citations (Scopus)

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 language	English
Pages (from-to)	153-163
Journal	Designs Codes and Cryptography
Volume	84
Issue number	1-2
DOIs	https://doi.org/10.1007/s10623-016-0241-4
Publication status	Published - 1 Jul 2017

Keywords

Adjacency matrix
Graph spectrum
Spectral characterizations

Access to Document

10.1007/s10623-016-0241-4

Cite this

@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{\u a}, {Sebastian M.} and Haemers, {Willem H.} and Vermette, {Jason R.}",

year = "2017",

month = jul,

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",

}

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

SN - 0925-1022

VL - 84

SP - 153

EP - 163

JO - Designs Codes and Cryptography

JF - Designs Codes and Cryptography

IS - 1-2

ER -

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

Abstract

Keywords

Access to Document

Fingerprint

Cite this