Spectral recognition of graphs and networks

Spektralna teorija grafova je matematiˇcka teorija koja grafove prouˇcava pomo´cu sopstvenih vrednosti i sopstvenih vektora matrica koje su im pridruˇzene. Posebno interesantni problemi ovog istraˇzivaˇckog domena jesu problemi spektralnog prepoznavanja grafova. Tu ubrajamo: karakterizaciju grafa sa zadatim spektrom, taˇcno ili pribliˇzno konstruisanje grafa sa zadatim spektrom, sliˇcnost grafova i perturbacije grafova. U disertaciji se u prvom redu razmatraju problemi sliˇcnosti grafova, gde se razlika pravi u zavisnosti od toga da li su ili ne poredbeni grafovi istog reda. Sliˇcnost grafova istog reda ustanovljava se izraˇcunavanjem spektralnih rastojanja, dok se, kada je reˇc o grafovima razliˇcitog reda, izraˇcunavaju i upored¯uju mere sliˇcnosti definisane za njihove ˇcvorove. Mere sliˇcnosti mogu i ne moraju da budu spektralno zasnovane, a poredbeni grafovi su u tom sluˇcaju obiˇcno grafovi sa velikim brojem ˇcvorova, pa se nazivaju mreˇzama. Disertacija sadrˇzi izvesne rezultate koji se odnose na Menhetn spektralno rastojanje grafova bazirano na matrici susedstva, Laplasovoj matrici i nenegativnoj Laplasovoj matrici. Predloˇzena je nova mera sliˇcnosti za ˇcvorove poredbenih mreˇza koja se zasniva na razlici funkcija generatrisa za brojeve zatvorenih ˇsetnji u ovim ˇcvorovima. Brojevi zatvorenih ˇsetnji izraˇcunavaju se, shodno novoj spektralnoj formuli, brojanjem razapinju´cih zatvorenih ˇsetnji u grafletima odgovaraju´cih grafova. Zapoˇceta je analiza spektralno-strukturalnih karakteristika digrafova u odnosu na spektar matrica AAT , odnosno ATA, gde je A matrica susedstva razmatranog digrafa. Generalizovan je pojam kospektralnosti, pa su u tom smislu dati neki rezultati vezani za kospektralnost digrafova i multigrafova u odnosu na matricu AAT i nenegativnu Laplasovu matricu, respektivno.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