Contribucions a l'estudi dels grafs i digrafs propers als de Moore

Abstract

El principal objectiu d'aquesta tesi és el de contribuir a l'estudi de l'existència i classificació dels grafs i digrafs que puguin admetre el màxim nombre de vèrtexs sota determinades condicions donats el grau i el diàmetre. Aquest estudi consta de tres parts ben diferenciades, una sobre digrafs i dos sobre grafs. En el treball relacionat amb els digrafs demostrem que els digrafs quasi de Moore de diàmetre k = 3 i qualsevol grau no existeixen. Així mateix provem la no existència dels digrafs quasi de Moore de diàmetre 4 i qualsevol grau assumint la irreductibilitat en Q[x] de certs polinomis. En quan als grafs ens hem centrat en l'existència dels de grau d, diàmetre 2 i defecte 2, anomenats (d,2,2)-grafs i assumint la irreductibilitat en Q[x] de certs polinomis provem que no existeixen per a cap grau. A més provem que no existeixen per a graus entre 4 i 50. Finalment estudiem els grafs radials de Moore de grau d i radi k. Proposem diferents mesures per classificar-los d'acord a la proximitat de les seves propietats a les d'un graf de Moore i ordenem segons aquestes mesures tots els grafs radials de Moore en els casos (d,k) = {(3,2), (3,3), (4,2)}.

El principal objetivo de esta tesis es el de contribuir al estudio de la existencia y clasificación de los grafos y digrafos que puedan admitir el máximo número de vértices bajo determinadas condiciones dados el grado y el diámetro. Este estudio consta de tres partes bien diferenciadas, una sobre digrafos y dos sobre grafos. En el trabajo relacionado con los digrafos demostramos que los digrafos casi de Moore de diámetro k = 3 y cualquier grado no existen. Asimismo probamos la no existencia de los digrafos casi de Moore de diámetro 4 y cualquier grado suponiendo la irreducibilidad en Q[x] de ciertos polinomios. En cuanto a los grafos nos hemos centrado en la existencia de los de grado d, diámetro 2 y defecto 2, llamados (d,2,2)-grafos y suponiendo la irreducibilidad en Q[x] de ciertos polinomios probamos que no existen para ningún grado. Además probamos que no existen para grados entre 4 y 50. Finalmente estudiamos los grafos radiales de Moore de grado d y radio k. Proponemos diferentes medidas para clasificarlos de acuerdo a la proximidad de sus propiedades a las de un grafo de Moore y ordenamos según estas medidas todos los grafos radiales de Moore en los casos (d, k) = {(3,2), (3,3), (4,2)}.

The main goal of this thesis is to contribute to the study of the existence and classification of graphs and digraphs that can achieve the maximum number of vertices under certain conditions given the degree and the diameter. This study consists of three differenciated parts, one on digraphs and two on graphs. The work on digraphs focuses on almost Moore digraphs. We prove that they do not exist for diameter 3 and any degree. Besides, we prove the non-existence of almost Moore digraphs of diameter 4 assuming the irreducibility in Q[x] of certain polynomials. Concerning graphs, we discuss the existence of graphs of degree d, diameter 2 and defect 2. Assuming the irreducibility in Q[x] of certain polynomials we prove their non existence. We also show they do not exist for degrees between 4 and 50. Finally we study radial Moore graphs of degree d and radius k. We propose different measures for classifying them in terms of their proximity to extremal properties of a Moore graph. By means of our measures, we are able to enumerate all radial Moore graphs for the cases (d, k) = {(3.2), (3.3), (4.2)}.