Normalment les grans xarxes d'interconnexió o de comunicacions estan dissenyades utilitzant tècniques de la teoria de grafs. Aquest treball presenta algunes contribucions a aquest tema. Concretament, presentem dues noves operacions: el "producte Jeràrquic" de grafs i el "producte Manhattan" de digrafs. El primer és una generalització del producte cartesià de grafs i ens permet construir algunes famílies amb un alt grau de jerarquia, com l'arbre binomial, que és una estructura de dades molt utilitzada en algorísmica. El segon dóna lloc a les conegudes Manhattan Street Networks, les quals han estat extensament estudiades i utilitzades per modelar algunes classes de xarxes òptiques. En el nostre treball, definim formalment i analitzem el cas multidimensional d'aquestes xarxes. Estudiem algunes propietats dels grafs o digrafs obtinguts mitjançant les dues operacions esmentades, especialment: els paràmetres estructurals (les propietats de l'operació, els subdigrafs induïts, la distribució de graus i l'estructura de digraf línia), els paràmetres mètrics (el diàmetre, el radi i la distància mitjana), la simetria (els grups d'automorfismes i els digrafs de Cayley), l'estructura de cicles (els cicles hamiltonians i la descomposició en cicles hamiltonians arc-disjunts) i les propietats espectrals (els valors i vectors propis). En el darrer cas, hem trobat, per exemple, que la família dels arbres binomials tenen tots els seus valors propis diferents, "omplint" tota la recta real. A més a més, mostrem la relació del seu conjunt de vectors propis amb els polinomis de Txebishev de segona espècie. També hem estudiat alguns protocols de comunicació, com els enrutaments locals i els algorismes de difusió. Finalment, presentem alguns models deterministes (com les xarxes Sierpinski i d'altres), els quals presenten algunes propietats pròpies de les xarxes complexes reals (com, per exemple, Internet). / Large interconnection or communication networks are usually designed and studied by using techniques from graph theory. This work presents some contributions to this subject. With this aim, two new operations are proposed: the "hierarchical product" of graphs and the "Manhattan product" of digraphs. The former can be seen as a generalization of the Cartesian product of graphs and allows us to construct some interesting families with a high degree of hierarchy, such as the well-know binomial tree, which is a data structure very used in the context of computer science. The latter yields, in particular, the known topologies of Manhattan Street Networks, which has been widely studied and used for modelling some classes of light-wave networks. In this thesis, a multidimensional approach is analyzed. Several properties of the graphs or digraphs obtained by both operations are dealt with, but special attention is paid to the study of their structural parameters (operation properties, induced subdigraphs, degree distribution and line digraph structure), metric parameters (diameter, radius and mean distance), symmetry (automorphism groups and Cayley digraphs), cycle structure (Hamilton cycles and arc-disjoint Hamiltonian decomposition) and spectral properties (eigenvalues and eigenvectors). For instance, with respect to the last issue, it is shown that some families of hypertrees have spectra with all different eigenvalues "filling up" all the real line. Moreover, we show the relationship between its eigenvector set and Chebyshev polynomials of the second kind. Also some protocols of communication, such as local routing and broadcasting algorithms, are addressed. Finally, some deterministic models (Sierpinsky networks and others) having similar properties as some real complex networks, such as the Internet, are presented.

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)}.

The orthography of Östergötland’s 11th century runic inscriptions varies widely, in part due to the lack of spelling norms at the time. This thesis seeks to identify other causes for the observed variation, based on the frequency and distribution of aspects of inscription orthography. The Old Norse words ræisa and stæin in the phrase “raised the stone” were analyzed based on the main vowel and its status as a monograph or digraph. The presence or absence of þ in inflected ræisa was also included as an indicator of age. All runic inscriptions in Östergötland with definite key word orthography were included, 169 in total. The analysis reveals that most inscriptions are clustered in three regions, each with a dominant vowel. By region, these are ei (west), i (central) and ai (east), with vowel consistency between ræisa and stæin the norm. The consonant þ in inflected ræisa is most common in the west and east. The vowel orthography together with the distribution of þ implies a relative chronology for Östergötland’s runic inscriptions, where the ongoing monophthongization is reflected in digraphs and monographs. The detailed orthography distribution of these variables shows that the main clusters align with the known 11th century quarries at Borghamn (west) and Vreta (central). Stoneworking at a shared site resulted in a transfer of knowledge, including runestone design and orthography which became a local norm as it spread. The lack of a unifying quarry in eastern Östergötland resulted in a more diverse local orthography, and possibly hampered the building of the first stone churches during the early 12th century. / Östergötlands runinskrifter från 1000-talet varierar stort i sin ortografi, delvis på grund av bristen på stavningsnormer när de ristades. Uppsatsen eftersträvar att identifiera andra orsaker för denna variation, baserat på frekvensen och distributionen av vissa aspekter i inskrifternas ortografi. De fornnordiska orden ræisa och stæin i inskriftsfrasen “reste sten” analyserades baserat på huvudvokalen samt om den var en monograf eller digraf. Användning av þ i böjda former av ræisa inkluderades som ett tecken på inskriftens ålder. Samtliga runinskrifter i Östergötland med en säker nyckelordsortografi analyserades, totalt 169 stycken. Resultaten visar att de flesta inskrifterna är grupperade i tre regioner som har varsin dominant vokal. Vanligast i väster är ei, i den centrala regionen råder i och i öster råder ai, med normen att samma vokal används i både ræisa och stæin. Konsonanten þ i böjd ræisa är vanligast i väster och i öster. Vokalortografin tillsammans med þ-distributionen indikerar en relativ kronologi för Östergötlands runinskrifter, där vokalernas monoftongering under 1000-talet återspeglas i digrafer och monografer. De analyserade variablernas distribution visar att huvudgrupperingarna sammanfaller med de kända stenbrotten från 1000-talet vid Borghamn (i väster) och Vreta (centrala regionen). Att stenarbetet skedde vid en gemensam site ledde till en omedveten kunskapsöverlämning mellan ristare. Inskriftsortografi kopierades och blev lokala normer allt efter att den spreds. Bristen på ett större stenbrott som informell, gemensam arbetsplats i östra Östergötland ledde till en mer varierad lokalortografi. Detta kan ha hindrat stenkyrkobygget lokalt under tidigt 1100-tal.