Resultados espectrais relacionados com a estrutura dos grafos

Nesta tese são estabelecidas novas propriedades espectrais de grafos com estruturas específicas, como sejam os grafos separados em cliques e independentes e grafos duplamente separados em independentes, ou ainda grafos com conjuntos (κ,τ)-regulares. Alguns invariantes dos grafos separados em cliques e independentes são estudados, tendo como objectivo limitar o maior valor próprio do espectro Laplaciano sem sinal. A técnica do valor próprio é aplicada para obter alguns majorantes e minorantes do índice do espectro Laplaciano sem sinal dos grafos separados em cliques e independentes bem como sobre o índice dos grafos duplamente separados em independentes. São fornecidos alguns resultados computacionais de modo a obter uma melhor percepção da qualidade desses mesmos extremos. Estudamos igualmente os grafos com um conjunto (κ,τ)-regular que induz uma estrela complementar para um valor próprio não-principal $. Além disso, é mostrado que $=κ-τ. Usando uma abordagem baseada nos grafos estrela complementares construímos, em alguns casos, os respectivos grafos maximais. Uma caracterização dos grafos separados em cliques e independentes que envolve o índice e as entradas do vector principal é apresentada tal como um majorante do número da estabilidade dum grafo conexo.

In this thesis new spectral properties of graphs with a specific structure (as split graphs, nested split and double split graphs as well as graphs with (κ,τ)-regular sets) are deduced. Some invariants of nested split graphs are studied in order to bound the largest eigenvalue of signless Laplacian spectra. The eigenvalue technique is applied to obtain some lower and upper bounds on the index of signless Laplacian spectra of nested split graphs as well as on the index of double nested graphs. Computational results are provided in order to gain a better insight of quality of these bounds. The graphs having a (κ,τ)-regular set which induces a star complement for a non-main eigenvalue $ are studied. Furthermore, it is shown that $= κ-τ. By the star complement technique, in some cases, maximal graphs with desired properties are constructed. A spectral characterization of families of split graphs involving its index and the entries of the principal eigenvector is given as well as an upper bound on the stability number of a connected graph.

Doutoramento em Matemática