The Planar Cubic Cayley Graphs
About this Title
Agelos Georgakopoulos
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
Table of Contents
Chapters
- Chapter 1. Introductory material and basic facts
- Chapter 2. The finite and 1-ended cubic planar Cayley graphs
- Chapter 3. The planar multi-ended Cayley graphs with 2 generators
- Chapter 4. The planar multi-ended Cayley graphs generated by 3 involutions
- Chapter 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.
- [Bab95] László Babai, Automorphism groups, isomorphism, reconstruction, Handbook of combinatorics, Vol. 1, 2, Elsevier Sci. B. V., Amsterdam, 1995, pp. 1447–1540. MR 1373683
- [Bab97] 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
- [Bog08] 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
- [BW03] C. Paul Bonnington and Mark E. Watkins, Planar embeddings with infinite faces, J. Graph Theory 42 (2003), no. 4, 257–275. MR 1963100
- [CWY09] 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
- [DD89] Warren Dicks and M. J. Dunwoody, Groups acting on graphs, Cambridge Studies in Advanced Mathematics, vol. 17, Cambridge University Press, Cambridge, 1989. MR 1001965
- [Die05] Reinhard Diestel, Graph theory, 3rd ed., Graduate Texts in Mathematics, vol. 173, Springer-Verlag, Berlin, 2005. MR 2159259
- [DK14] M. J. Dunwoody and B. Krön, Vertex Cuts, J. Graph Theory (2014), doi: 10.1002/jgt.21844.
- [Dro06] Carl Droms, Infinite-ended groups with planar Cayley graphs, J. Group Theory 9 (2006), no. 4, 487–496. MR 2243241
- [DSS98] 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
- [Dun] M. J. Dunwoody, Planar graphs and covers, Preprint available at http://www.personal.soton.ac.uk/mjd7/ .
- [Geo] Agelos Georgakopoulos, The planar cubic Cayley graphs of connectivity 2, European J. Combin. 64 (2017), 152–169. MR 3658826
- [Geo09] Agelos Georgakopoulos, Infinite Hamilton cycles in squares of locally finite graphs, Adv. Math. 220 (2009), no. 3, 670–705. MR 2483226
- [Geo12] A. Georgakopoulos, The Planar Cubic Cayley Graphs, Habilitationsschrift, Universität Hamburg, 2012.
- [Geo14] Agelos Georgakopoulos, Characterising planar Cayley graphs and Cayley complexes in terms of group presentations, European J. Combin. 36 (2014), 282–293. MR 3131895
- [GH15] A. Georgakopoulos and M. Hamann, The planar Cayley graphs are effectively enumerable, arXiv: 1506.03361.
- [Hoc13] W. Hochfellner, Hamilton-Kreise in kubischen planaren Cayley-Graphen, 2013, Master thesis, Technische Universität Graz.
- [Imr75] 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
- [Kro] B. Kron, Infinite faces and ends of almost transitive plane graphs, Preprint.
- [Mac67] A. M. Macbeath, The classification of non-euclidean plane crystallographic groups, Canad. J. Math. 19 (1967), 1192–1205. MR 0220838
- [Mit] 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.
- [Moh] B. Mohar, Personal communication.
- [Moh06] 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
- [Sab58] Gert Sabidussi, On a class of fixed-point-free graphs, Proc. Amer. Math. Soc. 9 (1958), 800–804. MR 0097068, https://doi.org/10.1090/S0002-9939-1958-0097068-7
- [Whi32] Hassler Whitney, Congruent Graphs and the Connectivity of Graphs, Amer. J. Math. 54 (1932), no. 1, 150–168. MR 1506881
- [Wil65] H. C. Wilkie, On non-Euclidean crystallographic groups, Math. Z. 91 (1966), 87–102. MR 0185013
- [ZVC80] 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