Grafos fortemente regulares e combinatória

Abstract

Nesta dissertação apresenta-se uma breve introdução à teoria dos grafos, designs combinatórios e geometrias finitas e estabelecem-se algumas relações entre estas estruturas combinatórias. No contexto dos grafos, é dada ênfase aos grafos fortemente regulares e às propriedades da matriz de adjacência. Nos designs combinatórios considera-se a construção de 1-designs e estudam-se algumas propriedades dos 2-designs e sistemas de Steiner. Apresentam-se várias ligações entre designs e grafos fortemente regulares e, em particular, mostra-se que o grafo dos blocos de um design quasi-simétrico é um grafo fortemente regular. Nas geometrias finitas consideram-se propriedades básicas dos planos afins e dos planos projectivos. Das propriedades destas geometrias, destacam-se a correspondência com determinadas famílias de 2-designs e a propriedade do grafo de incidência de um plano projectivo ser um grafo bipartido regular com cintura 6.

In this dissertation a brief introduction to graph theory, combinatorial designs and finite geometries is presented and some interconnections among those combinatorial structures are shown. In the context of graphs, some emphasis is given to strongly regular graphs and properties of the adjacency matrices. Properties of 2-designs and Steiner systems are studied as well as the construction of 1-designs. In addition, some connections between designs and strongly regular graphs are presented and it is shown that the block graph of a quasi-symmetric design is strongly regular. The finite geometries studied are the affine planes and the projective planes. Basic properties are considered, particularly the correspondence between those geometries and several families of 2-designs and the incidence graph of a projective plane being a regular bipartite graph with girth 6.