AMS eBook CollectionsOne of the world's most respected mathematical collections, available in digital format for your library or institution
The Planar Cubic Cayley Graphs
About this Title
Agelos Georgakopoulos, Mathematics Institute, University of Warwick, CV4 7AL, United Kingdom
Publication: Memoirs of the American Mathematical Society
Publication Year:
2017; Volume 250, Number 1190
ISBNs: 978-1-4704-2644-6 (print); 978-1-4704-4204-0 (online)
DOI: https://doi.org/10.1090/memo/1190
Published electronically: September 7, 2017
Keywords: Cayley graph,
planar graph,
planar presentation,
amalgamation
MSC: Primary 20F05; Secondary 05C10
Table of Contents
Chapters
- 1. Introductory material and basic facts
- 2. The finite and 1-ended cubic planar Cayley graphs
- 3. The planar multi-ended Cayley graphs with 2 generators
- 4. The planar multi-ended Cayley graphs generated by 3 involutions
- 5. Outlook
Abstract
We obtain a complete description of the planar cubic Cayley graphs, providing an explicit presentation and embedding for each of them. This turns out to be a rich class, comprising several infinite families. We obtain counterexamples to conjectures of Mohar, Bonnington and Watkins. Our analysis makes the involved graphs accessible to computation, corroborating a conjecture of Droms.- László Babai, Automorphism groups, isomorphism, reconstruction, Handbook of combinatorics, Vol. 1, 2, Elsevier Sci. B. V., Amsterdam, 1995, pp. 1447–1540. MR 1373683
- László Babai, The growth rate of vertex-transitive planar graphs, Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans, LA, 1997) ACM, New York, 1997, pp. 564–573. MR 1447704
- Oleg Bogopolski, Introduction to group theory, EMS Textbooks in Mathematics, European Mathematical Society (EMS), Zürich, 2008. Translated, revised and expanded from the 2002 Russian original. MR 2396717
- C. Paul Bonnington and Mark E. Watkins, Planar embeddings with infinite faces, J. Graph Theory 42 (2003), no. 4, 257–275. MR 1963100, DOI 10.1002/jgt.10089
- Qing Cui, Jian Wang, and Xingxing Yu, Hamilton circles in infinite planar graphs, J. Combin. Theory Ser. B 99 (2009), no. 1, 110–138. MR 2467822, DOI 10.1016/j.jctb.2008.05.002
- Warren Dicks and M. J. Dunwoody, Groups acting on graphs, Cambridge Studies in Advanced Mathematics, vol. 17, Cambridge University Press, Cambridge, 1989. MR 1001965
- Reinhard Diestel, Graph theory, 3rd ed., Graduate Texts in Mathematics, vol. 173, Springer-Verlag, Berlin, 2005. MR 2159259
- M. J. Dunwoody and B. Krön, Vertex Cuts, J. Graph Theory (2014), doi: 10.1002/jgt.21844.
- Carl Droms, Infinite-ended groups with planar Cayley graphs, J. Group Theory 9 (2006), no. 4, 487–496. MR 2243241, DOI 10.1515/JGT.2006.032
- Carl Droms, Brigitte Servatius, and Herman Servatius, Connectivity and planarity of Cayley graphs, Beiträge Algebra Geom. 39 (1998), no. 2, 269–282. MR 1642723
- M. J. Dunwoody, Planar graphs and covers, Preprint available at http://www.personal.soton.ac.uk/mjd7/ .
- Agelos Georgakopoulos, The planar cubic Cayley graphs of connectivity 2, European J. Combin. 64 (2017), 152–169. MR 3658826, DOI 10.1016/j.ejc.2017.04.005
- Agelos Georgakopoulos, Infinite Hamilton cycles in squares of locally finite graphs, Adv. Math. 220 (2009), no. 3, 670–705. MR 2483226, DOI 10.1016/j.aim.2008.09.014
- A. Georgakopoulos, The Planar Cubic Cayley Graphs, Habilitationsschrift, Universität Hamburg, 2012.
- Agelos Georgakopoulos, Characterising planar Cayley graphs and Cayley complexes in terms of group presentations, European J. Combin. 36 (2014), 282–293. MR 3131895, DOI 10.1016/j.ejc.2013.07.014
- A. Georgakopoulos and M. Hamann, The planar Cayley graphs are effectively enumerable, arXiv: 1506.03361.
- W. Hochfellner, Hamilton-Kreise in kubischen planaren Cayley-Graphen, 2013, Master thesis, Technische Universität Graz.
- Wilfried Imrich, On Whitney’s theorem on the unique embeddability of $3$-connected planar graphs, Recent advances in graph theory (Proc. Second Czechoslovak Sympos., Prague, 1974) Academia, Prague, 1975, pp. 303–306. (loose errata). MR 0384588
- B. Kron, Infinite faces and ends of almost transitive plane graphs, Preprint.
- A. M. Macbeath, The classification of non-euclidean plane crystallographic groups, Canadian J. Math. 19 (1967), 1192–1205. MR 220838, DOI 10.4153/CJM-1967-108-5
- K. Mitchell, Constructing semi-regular tilings, Talk given at the Spring 1995 Meeting of the Seaway Section of the MAA., http://people.hws.edu/mitchell/tilings/Part1.html.
- B. Mohar, Personal communication.
- Bojan Mohar, Tree amalgamation of graphs and tessellations of the Cantor sphere, J. Combin. Theory Ser. B 96 (2006), no. 5, 740–753. MR 2236509, DOI 10.1016/j.jctb.2006.02.003
- Gert Sabidussi, On a class of fixed-point-free graphs, Proc. Amer. Math. Soc. 9 (1958), 800–804. MR 97068, DOI 10.1090/S0002-9939-1958-0097068-7
- Hassler Whitney, Congruent Graphs and the Connectivity of Graphs, Amer. J. Math. 54 (1932), no. 1, 150–168. MR 1506881, DOI 10.2307/2371086
- H. C. Wilkie, On non-Euclidean crystallographic groups, Math. Z. 91 (1966), 87–102. MR 185013, DOI 10.1007/BF01110157
- Heiner Zieschang, Elmar Vogt, and Hans-Dieter Coldewey, Surfaces and planar discontinuous groups, Lecture Notes in Mathematics, vol. 835, Springer, Berlin, 1980. Translated from the German by John Stillwell. MR 606743