Cografos com intervalos livres de autovalores

Abstract

The search for distribution of eigenvalues of a graph on the real line is a topic of interest in Spectral Graph Theory. Taking into account that any interval of the real line contains some eigenvalues of a graph, since any root of a real-root monic polynomial with integer coefficients occurs as an eigenvalue of some tree, however, the class of cographs has eigenvalues free interval, that is, eigenvalues that do not belong to a specific given interval. From this, and motivated by the structural and spectral characteristics of these graphs, and with the aid of Diagonalization Algorithm we show that the eigenvalues of a cograph are free from the interval Ω = (−1, 0). Posteriorly, using second-order Chebyshev polynomials and Toeplitz matrices, we refine the interval to Ω = [−1−√2 2 , −1+√2 2 ], proving to be valid for any threshold graph, a subclass of cographs. We also present in this dissertation two algorithms that generate sequences of threshold graphs with eigenvalues-free from the intervals (𝑀�������,−1) and (0,𝑁�������), where 𝑀������� and 𝑁������� are real numbers given such that 𝑀������� < −1 and 𝑁������� > 0. And finally, we present certain classes of cographs that have eigenvalues-free of the interval Ω = [−1−√2 2 , −1+√2 2 𝛼�������𝑚�������𝑖�������𝑛�������], where 𝛼�������𝑚�������𝑖�������𝑛������� is the smallest natural number of a given sequence.