| Summary: | Um grafo excecional é um grafo conexo com menor valor próprio não inferior a -2 que não é grafo linha generalizado. Esta tese tem como objetivo apresentar uma nova técnica de construção de grafos regulares, com certas propriedades de natureza combinatória e espetral invariantes, e aplicá-la na construção de todos os grafos regulares excecionais. O trabalho encontra-se dividido em duas partes. Na primeira parte descreve- -se a nova técnica de construção de grafos regulares pela introdução de conjuntos (κ, τ )-regulares, designada de (κ, τ )-extensão, e define-se uma relação de ordem parcial entre grafos regulares. Mostra-se que a (κ, τ )- extensão de um grafo se reduz à construção de matrizes de incidência de um 1-design combinatório, para a qual se definem propriedades que previnem a construção de grafos isomorfos. Além disso, esta técnica permite a construção de grafos regulares com partição equilibrada e apresentam-se algumas propriedades espetrais destes grafos. Na segunda parte é feita uma breve descrição das três técnicas conhecidas para a construção dos grafos regulares excecionais. Posteriormente, aplicam-se as (κ, τ )-extensões na construção recursiva do conjunto dos grafos regulares excecionais, que se divide em três camadas. No caso das 1ª e 2ª camadas, os grafos obtêm-se por (0, 2)-extensões e, no caso da 3ª camada, por (1, 3)-extensões. Consequentemente, conclui-se que, para os grafos das 1ª e 2ª camadas o número de independência atinge o majorante de Hoffman e que o conjunto dos grafos regulares excecionais possui uma estrutura de conjunto parcialmente ordenado, sendo apresentando o respetivo diagrama de Hasse.
|
|---|