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)}.
| Identifer | oai:union.ndltd.org:TDX_UDL/oai:www.tdx.cat:10803/110573 |
| Date | 06 March 2013 |
| Creators | Conde Colom, Josep |
| Contributors | Gimbert i Quintilla, Joan, Miret, Josep M. (Josep Maria), Universitat de Lleida. Departament de Matemàtica |
| Publisher | Universitat de Lleida |
| Source Sets | Universitat de Lleida |
| Language | Catalan |
| Detected Language | Spanish |
| Type | info:eu-repo/semantics/doctoralThesis, info:eu-repo/semantics/publishedVersion |
| Format | 77 p., application/pdf |
| Source | TDX (Tesis Doctorals en Xarxa) |
| Rights | info:eu-repo/semantics/openAccess, L'accés als continguts d'aquesta tesi queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by-nc/3.0/es/ |
Page generated in 0.0031 seconds