Spectral characterizations of graphs

Aida Abiad Monge

Research output: ThesisDoctoral ThesisScientific

551 Downloads (Pure)

Abstract

Spectral graph theory studies the relation between structural properties of a graph and the eigenvalues of associated matrices. The spectrum (eigenvalues) contains a lot of information of the graph, but in general it does not determine it. Two graphs with the same spectrum for some type of matrix are called cospectral with respect to the corresponding matrix. Cospectral graphs help us understand “weaknesses” in identifying structures only using the spectrum. If a graph is not determined by the spectrum, this can be proved by constructing a nonisomorphic cospectral mate. The third chapter presents a new method to construct families of cospectral graphs that generalizes Godsil-McKay switching. For Godsil-McKay switching to work the graph needs a special structure. However, the presence of this structure does not imply that the graph is not determined by its spectrum; it may be that after switching the graph is isomorphic with the original one. Chapter four investigates this phenomenon, it shows some necessary conditions for isomorphism after switching and how they can be used to guarantee nonisomorphism after switching for some graph products. Chapter five shows how Godsil-McKay switching can be used to construct new strongly regular graphs with the same parameters as the symplectic graphs over the binary field, and it makes use of the 2-rank of the graph to prove nonisomorphism after switching. Chapter six gives a new contribution to the question: Can we see from the spectrum of a graph whether it is distance-regular?. Finally, chapter seven uses eigenvalue interlacing to obtain bounds for the sums of Laplacian eigenvalues of graphs, and characterize the case of equality. As a consequence, inequalities involving bounds for some well-known parameters of a graph are shown.
Original languageEnglish
QualificationDoctor of Philosophy
Awarding Institution
  • Tilburg University
Supervisors/Advisors
  • van Dam, Edwin, Promotor
  • Haemers, Willem H, Promotor
Award date19 Jun 2015
Place of PublicationTilburg
Publisher
Print ISBNs9789056684419
Publication statusPublished - 2015

Fingerprint

Graph in graph theory
Cospectral Graphs
Eigenvalue
Spectral Graph Theory
Graph Products
Laplacian Eigenvalues
Interlacing
Strongly Regular Graph
Structural Properties
Isomorphism
Equality
Isomorphic
Binary
Imply
Necessary Conditions
Generalise

Cite this

Abiad Monge, A. (2015). Spectral characterizations of graphs. Tilburg: CentER, Center for Economic Research.
Abiad Monge, Aida. / Spectral characterizations of graphs. Tilburg : CentER, Center for Economic Research, 2015. 104 p.
@phdthesis{047213fe66b34494a7e0cdfbf7eb64f2,
title = "Spectral characterizations of graphs",
abstract = "Spectral graph theory studies the relation between structural properties of a graph and the eigenvalues of associated matrices. The spectrum (eigenvalues) contains a lot of information of the graph, but in general it does not determine it. Two graphs with the same spectrum for some type of matrix are called cospectral with respect to the corresponding matrix. Cospectral graphs help us understand “weaknesses” in identifying structures only using the spectrum. If a graph is not determined by the spectrum, this can be proved by constructing a nonisomorphic cospectral mate. The third chapter presents a new method to construct families of cospectral graphs that generalizes Godsil-McKay switching. For Godsil-McKay switching to work the graph needs a special structure. However, the presence of this structure does not imply that the graph is not determined by its spectrum; it may be that after switching the graph is isomorphic with the original one. Chapter four investigates this phenomenon, it shows some necessary conditions for isomorphism after switching and how they can be used to guarantee nonisomorphism after switching for some graph products. Chapter five shows how Godsil-McKay switching can be used to construct new strongly regular graphs with the same parameters as the symplectic graphs over the binary field, and it makes use of the 2-rank of the graph to prove nonisomorphism after switching. Chapter six gives a new contribution to the question: Can we see from the spectrum of a graph whether it is distance-regular?. Finally, chapter seven uses eigenvalue interlacing to obtain bounds for the sums of Laplacian eigenvalues of graphs, and characterize the case of equality. As a consequence, inequalities involving bounds for some well-known parameters of a graph are shown.",
author = "{Abiad Monge}, Aida",
year = "2015",
language = "English",
isbn = "9789056684419",
series = "CentER Dissertation Series",
publisher = "CentER, Center for Economic Research",
school = "Tilburg University",

}

Abiad Monge, A 2015, 'Spectral characterizations of graphs', Doctor of Philosophy, Tilburg University, Tilburg.

Spectral characterizations of graphs. / Abiad Monge, Aida.

Tilburg : CentER, Center for Economic Research, 2015. 104 p.

Research output: ThesisDoctoral ThesisScientific

TY - THES

T1 - Spectral characterizations of graphs

AU - Abiad Monge, Aida

PY - 2015

Y1 - 2015

N2 - Spectral graph theory studies the relation between structural properties of a graph and the eigenvalues of associated matrices. The spectrum (eigenvalues) contains a lot of information of the graph, but in general it does not determine it. Two graphs with the same spectrum for some type of matrix are called cospectral with respect to the corresponding matrix. Cospectral graphs help us understand “weaknesses” in identifying structures only using the spectrum. If a graph is not determined by the spectrum, this can be proved by constructing a nonisomorphic cospectral mate. The third chapter presents a new method to construct families of cospectral graphs that generalizes Godsil-McKay switching. For Godsil-McKay switching to work the graph needs a special structure. However, the presence of this structure does not imply that the graph is not determined by its spectrum; it may be that after switching the graph is isomorphic with the original one. Chapter four investigates this phenomenon, it shows some necessary conditions for isomorphism after switching and how they can be used to guarantee nonisomorphism after switching for some graph products. Chapter five shows how Godsil-McKay switching can be used to construct new strongly regular graphs with the same parameters as the symplectic graphs over the binary field, and it makes use of the 2-rank of the graph to prove nonisomorphism after switching. Chapter six gives a new contribution to the question: Can we see from the spectrum of a graph whether it is distance-regular?. Finally, chapter seven uses eigenvalue interlacing to obtain bounds for the sums of Laplacian eigenvalues of graphs, and characterize the case of equality. As a consequence, inequalities involving bounds for some well-known parameters of a graph are shown.

AB - Spectral graph theory studies the relation between structural properties of a graph and the eigenvalues of associated matrices. The spectrum (eigenvalues) contains a lot of information of the graph, but in general it does not determine it. Two graphs with the same spectrum for some type of matrix are called cospectral with respect to the corresponding matrix. Cospectral graphs help us understand “weaknesses” in identifying structures only using the spectrum. If a graph is not determined by the spectrum, this can be proved by constructing a nonisomorphic cospectral mate. The third chapter presents a new method to construct families of cospectral graphs that generalizes Godsil-McKay switching. For Godsil-McKay switching to work the graph needs a special structure. However, the presence of this structure does not imply that the graph is not determined by its spectrum; it may be that after switching the graph is isomorphic with the original one. Chapter four investigates this phenomenon, it shows some necessary conditions for isomorphism after switching and how they can be used to guarantee nonisomorphism after switching for some graph products. Chapter five shows how Godsil-McKay switching can be used to construct new strongly regular graphs with the same parameters as the symplectic graphs over the binary field, and it makes use of the 2-rank of the graph to prove nonisomorphism after switching. Chapter six gives a new contribution to the question: Can we see from the spectrum of a graph whether it is distance-regular?. Finally, chapter seven uses eigenvalue interlacing to obtain bounds for the sums of Laplacian eigenvalues of graphs, and characterize the case of equality. As a consequence, inequalities involving bounds for some well-known parameters of a graph are shown.

M3 - Doctoral Thesis

SN - 9789056684419

T3 - CentER Dissertation Series

PB - CentER, Center for Economic Research

CY - Tilburg

ER -

Abiad Monge A. Spectral characterizations of graphs. Tilburg: CentER, Center for Economic Research, 2015. 104 p. (CentER Dissertation Series).