Una revisión a las propiedades y familia de expansores en grafos de Cayley

• Cortes Garcia, Christian Camilo ^[1]
  1. [1] Universidad Carlos III de Madrid

     Universidad Carlos III de Madrid

     Madrid, España

     
• Localización: Selecciones Matemáticas, ISSN-e 2411-1783, Vol. 7, Nº. 2, 2020 (Ejemplar dedicado a: August - December), págs. 323-339
• Idioma: español
• DOI: 10.17268/sel.mat.2020.02.14
• Títulos paralelos:
  • A review of Cayley graph properties and expander family
• Enlaces
  • Texto completo (pdf)
• Resumen
  • español

    En este trabajo se introducen algunos conceptos usados en teoría de grafos, tales como grafos dirigidos, no dirigidos, conexos, arboles, regulares u operadores gradientes, divergentes o laplacianos, y relaciones existentes entre el diámetro del grafo, o el valor segundo propio más grande de su matriz de adyacencia, respecto a la constante de Cheeger para identificar grafos expansores k-regulares. Con esos lineamientos definidos, se introducen algunas propiedades en grafos de Cayley, con ejemplos ilustrativos, y metodologías para identificar si el grafo correspondiente es k-regular o un árbol dirigido. Finalmente, se relacionan grafos expansores de Cayley con su diámetro o el segundo valor propio más grande.

  • English

    In this paper some concepts used in graph theory are introduced, such as directed, undirected, connected, tree, regular or gradient, divergent or Laplacian graphs, and relationships between the diameter of the graph, or the largest second proper value of its adjacency matrix, with respect to the Cheeger constant to identify expander graphs k-regular. With these guidelines defined, some properties are introduced in Cayley graphs, with illustrative examples, and methodologies to identify if the corresponding graph is k-regular or a directed tree. Finally, Cayley expander graphs are related to their diameter or the second largest eigenvalue.

• Referencias bibliográficas
  • Delorme C. Cayley digraphs and graphs. European J. of Combinatorics. 2013; 34:1307-1315.
  • Post O. Analysis on Graphs. ICMAT: Lecture notes summarise given at Escuela JAE de Matemáticas; 2017.
  • Krebs M, Shaheen A. Expander families and Cayley graphs: a beginner’s guide.Oxford: Oxford University Press; 2011.
  • Griñá D. Grafos de Cayley.[Diss.]: Universidad Politecnica de Madrid; 2017.
  • Serre JP. Trees. Springer Monographs in Mathematics. Berlin: Springer-Verlag; 1980.
  • Biggs N, Norman B. Algebraic graph theory. Cambridge: Cambridge university press; 1993.
  • Pflegpeter M. Cayley-graphs and Free Groups[Bachelor Thesis]. Vienna: Slovenian-Austrian Cooperation project (OAD) Ljubljana; 2010.
  • Babai L. Spectra of Cayley graphs. J. of Combinatorial Theory, Series B. 1979; 27(2):180-189.
  • Petteri K. Eigenvectors and Spectra of Cayley Graph. Helsinki: Manuscript for a seminar given at Helsinki University of Technology; 2002.