Abstract:

Spectral graph theory is a mathematical theory where graphs are considered by
means of the eigenvalues and the corresponding eigenvectors of the matrices that
are assigned to them. The spectral recognition problems are of particular interest.
Between them we can distinguish: characterizations of graphs with a given spectrum,
exact or approximate constructions of graphs with a given spectrum, similarity of
graphs and perturbations of graphs. In this dissertation we are primarily interested
for the similarity of graphs, where graphs with the same number of vertices and
graphs of different orders are considered.
Similarity of graphs of equal orders can be established by computation of the
spectral distances between them, while for graphs with different number of vertices
the measures of similarity are introduced. In that case, graphs under study are
usually very large and they are denoted as networks, while the measures of similarity
can be spectraly based. Some mathematical results on the Manhattan spectral
distance of graphs based on the adjacency matrix, Laplacian and signless Laplacian
matrix are given in this dissertation. A new measure of similarity for the vertices of
the networks under study is proposed. It is based on the difference of the generating
functions for the numbers of closed walks in the vertices of networks. These closed
walks are calculated according to the new spectral formula which enumerates the
numbers of spanning closed walks in the graphlets of the corresponding graphs.
The problem of the characterization of a digraph with respect to the spectrum
of AAT , apropos ATA, where A is the adjacency matrix of a digraph, is introduced.
The notion of cospectrality is generalized, and so the cospectrality between some
particular digraphs with respect to the matrix AAT and multigraphs with respect
to the signless Laplacian matrix is considered. 