A review of Cayley graph properties and expander family

Authors

  • Christian Camilo Cortes Garcia Departamento de matemáticas, Universidad Carlos III de Madrid, Madrid - España. Facultad de Ciencias Exactas y Naturales, Universidad Surcolombiana, Neiva, Colombia. http://orcid.org/0000-0002-8955-4530

DOI:

https://doi.org/10.17268/sel.mat.2020.02.14

Keywords:

Generator set, isoperimetric constant, transitive vertex graph, group, free group

Abstract

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.

Author Biography

Christian Camilo Cortes Garcia, Departamento de matemáticas, Universidad Carlos III de Madrid, Madrid - España. Facultad de Ciencias Exactas y Naturales, Universidad Surcolombiana, Neiva, Colombia.

Facultad de ciencias exactas y naturales, Universidad Surcolombiana, Neiva-Colombia.
Departamento de matematicas, Universidad Carlos III de Madrid, Madrid - España.

References

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

Published

2020-12-25

How to Cite

Cortes Garcia, C. C. (2020). A review of Cayley graph properties and expander family. Selecciones Matemáticas, 7(02), 323-339. https://doi.org/10.17268/sel.mat.2020.02.14

Issue

Vol. 7 No. 02 (2020): August - December

Section

Review

License

The authors who publish in this journal accept the following conditions:
1. The authors retain the copyright and assign to the journal the right of the first publication, with the work registered with the Creative Commons Attribution License,Atribución 4.0 Internacional (CC BY 4.0) which allows third parties to use what is published whenever they mention the authorship of the work And to the first publication in this magazine.
2. Authors may make other independent and additional contractual arrangements for non-exclusive distribution of the version of the article published in this journal (eg, include it in an institutional repository or publish it in a book) provided they clearly state that The paper was first published in this journal.
3. Authors are encouraged to publish their work on the Internet (for example, on institutional or personal pages) before and during the review and publication process, as it can lead to productive exchanges and to a greater and more rapid dissemination Of the published work.