Utilize este identificador para referenciar este registo:
http://hdl.handle.net/10773/14814
Título: | Determinação de grafos regulares excecionais com recurso a (K, T)-extensões |
Outros títulos: | Determination of regular exceptional graphs by (K, T)-extensions |
Autor: | Magalhães, Inês Monteiro Barbedo de |
Orientador: | Cardoso, Domingos Moreira Rama, Paula Cristina Roque da Silva |
Palavras-chave: | Matemática Teoria de grafos Análise combinatória |
Data de Defesa: | 2015 |
Editora: | Universidade de Aveiro |
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´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´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´técnica permite
a construção de grafos regulares com partição equilibrada e apresentam-se
algumas propriedades espetrais destes grafos. Na segunda parte ´e 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 1a e 2a camadas, os grafos obtém-se
por (0, 2)-extensões e, no caso da 3a camada, por (1, 3)-extensões. Consequentemente,
conclui-se que, para os grafos das 1a e 2a 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. An exceptional graph is a connected graph with least eigenvalue greater than or equal to -2 which is not a generalized line graph. The aim of this thesis is to present a new technique for the construction of regular graphs, with certain spectral and combinatorial invariant properties, and to apply it in the construction of all regular exceptional graphs. The work is divided into two parts. The first part describes a new construction technique that introduces (κ, τ )-regular sets in regular graphs, called (κ, τ )-extension, and defines a partial order between regular graphs. It is shown that the process of extending a graph is reduced to the construction of the incidence matrix of a combinatorial 1-design, considering several rules to prevent the production of isomorphic graphs. Furthermore, this technique allows the construction of regular graphs with an equitable partition and some spectral properties of these graphs are presented. The second part starts with a brief description of the three techniques, previously known for the construction of regular exceptional graphs. Later, the (κ, τ )-extensions are applied to the recursive construction of the set of regular exceptional graphs, which are partitioned in three layers. In the case of the 1st and 2nd layers, graphs are obtained by (0, 2)-extensions and in the case of 3rd layer, by (1, 3)-extensions. Therefore, we conclude that, the independence number attains Hoffman’s upper bound for the graphs of 1st and 2nd layers and the set of regular exceptional graphs has a partially ordered set structure whose Hasse diagram is presented. |
Descrição: | Doutoramento em Matemática e Aplicações |
URI: | http://hdl.handle.net/10773/14814 |
Aparece nas coleções: | UA - Teses de doutoramento DMat - Teses de doutoramento |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
Determinação de grafos regulares excecionais.pdf | 923.15 kB | Adobe PDF | Ver/Abrir |
Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.