Abstract
Original language  English 

Qualification  Doctor of Philosophy 
Awarding Institution 

Supervisors/Advisors 

Award date  19 Jun 2015 
Place of Publication  Tilburg 
Publisher  
Print ISBNs  9789056684419 
Publication status  Published  2015 
Fingerprint
Cite this
}
Spectral characterizations of graphs. / Abiad Monge, Aida.
Tilburg : CentER, Center for Economic Research, 2015. 104 p.Research output: Thesis › Doctoral Thesis › Scientific
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 GodsilMcKay switching. For GodsilMcKay 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 GodsilMcKay 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 2rank 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 distanceregular?. 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 wellknown 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 GodsilMcKay switching. For GodsilMcKay 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 GodsilMcKay 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 2rank 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 distanceregular?. 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 wellknown parameters of a graph are shown.
M3  Doctoral Thesis
SN  9789056684419
T3  CentER Dissertation Series
PB  CentER, Center for Economic Research
CY  Tilburg
ER 