Determinação de grafos regulares excecionais com recurso a (k,t)-extensões
Teses
Visão geral
Pesquisas
Ver Todos
Visão geral
resumo
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.
