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

• Autores: Víctor Diego Gutiérrez
• Directores de la Tesis: Miguel Ángel Fiol Mora (dir. tes.) , Josep Fàbrega Canudas (codir. tes.)
• Lectura: En la Universitat Politècnica de Catalunya (UPC) ( España ) en 2017
• Idioma: español
• Tribunal Calificador de la Tesis: Carlos Marijuán López (presid.) , Ignacio López Lorenzo (secret.) , Ernest Garriga Valle (voc.)
• Texto completo no disponible (Saber más ...)
• Resumen

  • 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.