Academic literature on the topic 'Spectrum of graphs'

Graphs whose spectrum belongs to the interval [-2,2] are called Smith graphs. The structure of a Smith graph with a given spectrum depends on a system of Diophantine linear algebraic equations. We have established in [1] several properties of this system and showed how it can be simplified and effectively applied. In this way a spectral theory of Smith graphs has been outlined. In the present paper we introduce cospectrality graphs for Smith graphs and study their properties through examples and theoretical consideration. The new notion is used in proving theorems on cospectrality of Smith graphs. In this way one can avoid the use of the mentioned system of Diophantine linear algebraic equations.

We extend spectral graph theory from the integral circulant graphs with prime power order to a Cayley graph over a finite chain ring and determine the spectrum and energy of such graphs. Moreover, we apply the results to obtain the energy of some gcd-graphs on a quotient ring of a unique factorisation domain.

At some time, in the childhood of spectral graph theory, it was conjectured that non-isomorphic graphs have different spectra, i.e. that graphs are characterized by their spectra. Very quickly this conjecture was refuted and numerous examples and families of non-isomorphic graphs with the same spectrum (cospectral graphs) were found. Still some graphs are characterized by their spectra and several mathematical papers are devoted to this topic. In applications to computer sciences, spectral graph theory is considered as very strong. The benefit of using graph spectra in treating graphs is that eigenvalues and eigenvectors of several graph matrices can be quickly computed. Spectral graph parameters contain a lot of information on the graph structure (both global and local) including some information on graph parameters that, in general, are computed by exponential algorithms. Moreover, in some applications in data mining, graph spectra are used to encode graphs themselves. The Euclidean distance between the eigenvalue sequences of two graphs on the same number of vertices is called the spectral distance of graphs. Some other spectral distances (also based on various graph matrices) have been considered as well. Two graphs are considered as similar if their spectral distance is small. If two graphs are at zero distance, they are cospectral. In this sense, cospectral graphs are similar. Other spectrally based measures of similarity between networks (not necessarily having the same number of vertices) have been used in Internet topology analysis, and in other areas. The notion of spectral distance enables the design of various meta-heuristic (e.g., tabu search, variable neighbourhood search) algorithms for constructing graphs with a given spectrum (spectral graph reconstruction). Several spectrally based pattern recognition problems appear in many areas (e.g., image segmentation in computer vision, alignment of protein-protein interaction networks in bio-informatics, recognizing hard instances for combinatorial optimization problems such as the travelling salesman problem). We give a survey of such and other graph spectral recognition techniques used in computer sciences.

A signed graph consists of a (simple) graph G=(V,E) together with a function ? : E ? {+,-} called signature. Matrices can be associated to signed graphs and the question whether a signed graph is determined by the set of its eigenvalues has gathered the attention of several researchers. In this paper we study the spectral determination with respect to the Laplacian spectrum of signed ?-graphs. After computing some spectral invariants and obtain some constraints on the cospectral mates, we obtain some non isomorphic signed graphs cospectral to signed ?-graphs and we study the spectral characterization of the signed ?-graphs containing a triangle.