dc.contributor
Universitat de Lleida. Departament de Matemàtica
dc.contributor.author
Conde Colom, Josep
dc.date.accessioned
2013-04-24T07:10:25Z
dc.date.available
2013-04-24T07:10:25Z
dc.date.issued
2013-03-06
dc.identifier.uri
http://hdl.handle.net/10803/110573
dc.description.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)}.
cat
dc.description.abstract
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)}.
spa
dc.description.abstract
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)}.
eng
dc.format.mimetype
application/pdf
dc.publisher
Universitat de Lleida
dc.rights.license
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/
dc.rights.uri
http://creativecommons.org/licenses/by-nc/3.0/es/
*
dc.source
TDX (Tesis Doctorals en Xarxa)
dc.subject
Digraf quasi de Moore
dc.subject
Polinomi característic
dc.subject
Graf radial de Moore
dc.subject
Digrafo casi de Moore
dc.subject
Polinomio característico
dc.subject
Grafo radial de Moore
dc.subject
Almost Moore digraph
dc.subject
Characteristic polynomial
dc.subject
Radially Moore graph
dc.title
Contribucions a l'estudi dels grafs i digrafs propers als de Moore
dc.type
info:eu-repo/semantics/doctoralThesis
dc.type
info:eu-repo/semantics/publishedVersion
dc.contributor.codirector
Gimbert i Quintilla, Joan
dc.contributor.codirector
Miret, Josep M. (Josep Maria)
dc.rights.accessLevel
info:eu-repo/semantics/openAccess
dc.identifier.dl
L.284-2013