Graphs with few eigenvalues. An interplay between combinatorics and algebra

Research output: ThesisDoctoral ThesisScientific

355 Downloads (Pure)

Abstract

Two standard matrix representations of a graph are the adjacency matrix and the Laplace matrix. The eigenvalues of these matrices are interesting parameters of the graph. Graphs with few eigenvalues in general have nice combinatorial properties and a rich structure. A well investigated family of such graphs comprises the strongly regular graphs (the regular graphs with three eigenvalues), and we may see other graphs with few eigenvalues as algebraic generalizations of such graphs. We study the (nonregular) graphs with three adjacency eigenvalues, graphs with three Laplace eigenvalues, and regular graphs with four eigenvalues. The last ones are also studied in relation with three-class association schemes. We also derive bounds on the diameter and on the size of special subsets in terms of the eigenvalues of the graph. Included are lists of feasible parameter sets of graphs with three Laplace eigenvalues, regular graphs with four eigenvalues, and three-class association schemes.
Original languageEnglish
QualificationDoctor of Philosophy
Awarding Institution
  • Tilburg University
Supervisors/Advisors
  • Tijs, S.H., Promotor
  • Haemers, Willem H, Promotor
Award date4 Oct 1996
Place of PublicationTilburg
Publisher
Publication statusPublished - 1996

Fingerprint

Combinatorics
Eigenvalue
Algebra
Graph in graph theory
Regular Graph
Laplace
Association Scheme
Graph Eigenvalues
Strongly Regular Graph
Matrix Representation
Adjacency
Adjacency Matrix
Subset

Cite this

van Dam, E.R.. / Graphs with few eigenvalues. An interplay between combinatorics and algebra. Tilburg : CentER, Center for Economic Research, 1996. 146 p.
@phdthesis{93358bfe49d34164bc75c858e34f9e4a,
title = "Graphs with few eigenvalues. An interplay between combinatorics and algebra",
abstract = "Two standard matrix representations of a graph are the adjacency matrix and the Laplace matrix. The eigenvalues of these matrices are interesting parameters of the graph. Graphs with few eigenvalues in general have nice combinatorial properties and a rich structure. A well investigated family of such graphs comprises the strongly regular graphs (the regular graphs with three eigenvalues), and we may see other graphs with few eigenvalues as algebraic generalizations of such graphs. We study the (nonregular) graphs with three adjacency eigenvalues, graphs with three Laplace eigenvalues, and regular graphs with four eigenvalues. The last ones are also studied in relation with three-class association schemes. We also derive bounds on the diameter and on the size of special subsets in terms of the eigenvalues of the graph. Included are lists of feasible parameter sets of graphs with three Laplace eigenvalues, regular graphs with four eigenvalues, and three-class association schemes.",
author = "{van Dam}, E.R.",
year = "1996",
language = "English",
series = "CentER Dissertation Series",
publisher = "CentER, Center for Economic Research",
school = "Tilburg University",

}

van Dam, ER 1996, 'Graphs with few eigenvalues. An interplay between combinatorics and algebra', Doctor of Philosophy, Tilburg University, Tilburg.

Graphs with few eigenvalues. An interplay between combinatorics and algebra. / van Dam, E.R.

Tilburg : CentER, Center for Economic Research, 1996. 146 p.

Research output: ThesisDoctoral ThesisScientific

TY - THES

T1 - Graphs with few eigenvalues. An interplay between combinatorics and algebra

AU - van Dam, E.R.

PY - 1996

Y1 - 1996

N2 - Two standard matrix representations of a graph are the adjacency matrix and the Laplace matrix. The eigenvalues of these matrices are interesting parameters of the graph. Graphs with few eigenvalues in general have nice combinatorial properties and a rich structure. A well investigated family of such graphs comprises the strongly regular graphs (the regular graphs with three eigenvalues), and we may see other graphs with few eigenvalues as algebraic generalizations of such graphs. We study the (nonregular) graphs with three adjacency eigenvalues, graphs with three Laplace eigenvalues, and regular graphs with four eigenvalues. The last ones are also studied in relation with three-class association schemes. We also derive bounds on the diameter and on the size of special subsets in terms of the eigenvalues of the graph. Included are lists of feasible parameter sets of graphs with three Laplace eigenvalues, regular graphs with four eigenvalues, and three-class association schemes.

AB - Two standard matrix representations of a graph are the adjacency matrix and the Laplace matrix. The eigenvalues of these matrices are interesting parameters of the graph. Graphs with few eigenvalues in general have nice combinatorial properties and a rich structure. A well investigated family of such graphs comprises the strongly regular graphs (the regular graphs with three eigenvalues), and we may see other graphs with few eigenvalues as algebraic generalizations of such graphs. We study the (nonregular) graphs with three adjacency eigenvalues, graphs with three Laplace eigenvalues, and regular graphs with four eigenvalues. The last ones are also studied in relation with three-class association schemes. We also derive bounds on the diameter and on the size of special subsets in terms of the eigenvalues of the graph. Included are lists of feasible parameter sets of graphs with three Laplace eigenvalues, regular graphs with four eigenvalues, and three-class association schemes.

M3 - Doctoral Thesis

T3 - CentER Dissertation Series

PB - CentER, Center for Economic Research

CY - Tilburg

ER -

van Dam ER. Graphs with few eigenvalues. An interplay between combinatorics and algebra. Tilburg: CentER, Center for Economic Research, 1996. 146 p. (CentER Dissertation Series).