On some spectral and combinatorial properties of distance-regular graphs and their generalizations

Abstract

In this work we present the study we did in Graph Theory. In the firsts chapteres of the tesis we study the pieces of information that can be obtained from a graph: the spectrum of the adjacency matrix, the preintersection numbers, the predistance polynomials and the average number of closed walks. Some of this pieces of information are direct generalizations of the intersection numbers or the predistance polynomials defined in the distance-regular graphs. We prove that the multiple properties that these pieces of information have in distance-regular graphs hold also in their generalizations, and these properties can be applied to any other graph.

We also prove that the distinct pieces of information (even if their nature is algebraic or combinatorial) are equivalent. That is, we can obtain each one of the pieces in terms of each other; proving in this way that the properties of the graph derived from each one of the pieces can be also obtained in terms of each one of the other. We dedicate a chapter of the tesis to describe completly the especific procedures with which obtain each piece of inforation in terms of the others.

In this tesis we introduce the "distance mean-regular" graphs. These graphs are a generalization of the distance-regular graphs. In this occasion, we demand to the graph combinatorial properties and we generalizate the algebraic properties of the distance-regular graphs. We generalizate the spectrum of a graph to introduce the "pseudo-spectrum" and we generalizate the Bose-Mesner algebra in distinct matrix algebras. The study of these generalizations, as well as the study of the relation between them, give us combinatorial and algebraic properties.

In the final part of the tesis we study the vertex-isoperimetric problem in the Johnson Graph J(n,m). We solve completly the problem for some particular cases: J(n,1), J(n,2), J(2m-2,m), as well as their symetrics J(n,n-2) and J(2m+2,m). The solution for these cases are the initial segments of the colexicographic order. This order is also the solution for small cardinals in every graph of this family, as well as for the asymptotic behaviour of the parameters n and m.

However, this solution is not the optimal solution for every cardinal in every graph J(n,m). We prove and give an infinity family of counterexamples for which the initial segment of the colexicographic order is not optimal in terms of the vertex-isoperimetric problem.

En este documento presentamos el estudio realizado en Teoría de Grafos. En los primeros capítulos de la tesis estudiamos las distinetas piezas de información que se pueden obtener de un grafo: el espectro de su matriz de adyacencia, los números de preintersección, los polinomios predistancia o la cantidad media de caminos cerrados. Algunos de estas piezas de información son generalizaciones directas de los números de intersección o los pollinomios distancia definidos en los grafos distancia-regulares. Demostramos que las múltiples propiedades que tienen estas piezas de información en los grafos distancia-regulares se mantienen también en sus generalizaciones, pudiendo aplicar estas propiedades a todo tipo de grafos. Demostramos también que las ditintas piezas de información (ya sean de naturaleza algebraica o combinatoria) son equivalentes. Es decir, podemos obtener cada una de estas piezas en términos de cada una de las otras; probando así que las propiedades del grafo derivadas de cada una de estas piezas puede ser obtenida en términos de cada una de las otras. Dedicamos uno de los capítulos de la tesis a describir cuáles son los procesos específicos completos mediante los cuales obtener cada pieza de información en función de las otras. En esta tesis introducimos también los grafos distance mean-regular. Estos grafos son una generalización de los grafos distancia-regulares. En esta ocasión, al grafo se le exigen propiedades combinatorias y generalizamos las propiedades algebraicas de los grafos distancia-regulares. Generalizamos el espectro de un grafo para introducir el "pseudo-espectro" y generalizamos el álgebra de Bose-Mesner en distintas álgebras de matrices. El estudio de estas generalizaciones, así cómo su relación entre ellas nos proporciona propiedades combinatorias y algebraicas del grafo. En la parte final de la tesis estudiamos el problema isoperimétrico de vértices en el Grafo de Johnson J(n,m). Solucionamos el problema completamente para varios casos particulares: J(n,1), J(n,2) y J(2m-2,m), así como sus simétricos J(n,n-2) y J(2m+2,m). La solución para estos casos son los segmentos iniciales del orden colexicográfico. Este orden es también la solución para cardinales pequeños en todos los grafos de esta familia, así como para el comportamiento asimptótico de los parámetros n y m. Sin embargo, esta solución no es la solución óptima en todos cardinales de todos los grafos J(n,m). Demostramos y damos una familia infinita de contraejemplos para los cuales el segmento inicial de orden colexicográfico no es óptimo en términos del problema isoperimétrico de vértices