Una revisión a las propiedades y familia de expansores en grafos de Cayley
DOI:
https://doi.org/10.17268/sel.mat.2020.02.14Palabras clave:
Conjunto generador, constante isoperimétrica, grafo vértice transitivo, grupo, grupo libreResumen
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.
Citas
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.
Descargas
Publicado
Cómo citar
Número
Sección
Licencia
Los autores/as que publiquen en esta revista aceptan las siguientes condiciones:
- Los autores/as conservan los derechos de autor y ceden a la revista el derecho de la primera publicación, con el trabajo registrado con la licencia de atribución de Creative CommonsAtribución 4.0 Internacional (CC BY 4.0) , que permite a terceros utilizar lo publicado siempre que mencionen la autoría del trabajo y a la primera publicación en esta revista.
- Los autores/as pueden realizar otros acuerdos contractuales independientes y adicionales para la distribución no exclusiva de la versión del artículo publicado en esta revista (p. ej., incluirlo en un repositorio institucional o publicarlo en un libro) siempre que indiquen claramente que el trabajo se publicó por primera vez en esta revista.
- Se permite y recomienda a los autores/as a publicar su trabajo en Internet (por ejemplo en páginas institucionales o personales) antes y durante el proceso de revisión y publicación, ya que puede conducir a intercambios productivos y a una mayor y más rápida difusión del trabajo publicado(Consultar: efecto del acceso abierto).
