Una revisión a las propiedades y familia de expansores en grafos de Cayley
DOI:
https://doi.org/10.17268/sel.mat.2020.02.14Palavras-chave:
Conjunto generador, constante isoperimétrica, grafo vértice transitivo, grupo, grupo libreResumo
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.
Referências
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.
Downloads
Publicado
Como Citar
Edição
Seção
Licença
Os autores que publicam nesta revista aceitam as seguintes condições:
Os autores mantêm os direitos autorais e atribuem à revista o direito da primeira publicação, com o trabalho registrado com a licença de atribuição Creative Commons Atribución 4.0 Internacional (CC BY 4.0), que permite que terceiros usem o material publicado sempre que mencionarem a autoria do trabalho e os direitos autorais. Primeira publicação nesta revista.
Os autores podem fazer outros acordos contratuais independentes e adicionais para a distribuição não exclusiva da versão do artigo publicada nesta revista (por exemplo, incluí-la em um repositório institucional ou publicá-la em um livro), desde que afirme claramente que o trabalho Foi publicado nesta revista.
É permitido e recomendado aos autores que publiquem seus trabalhos na Internet (por exemplo, em páginas institucionais ou pessoais) antes e durante o processo de revisão e publicação, pois isso pode levar a trocas produtivas e a uma disseminação maior e mais rápida do trabalho. publicado (Consultar: efeito do acesso aberto).
