Splitting groups with cubic Cayley graphs of connectivity two

Miraftab, Babak; Stavropoulos, Konstantinos

Algebraic Combinatorics, Tome 4 (2021) no. 6, pp. 971-987.

A group $G$ splits over a subgroup $C$ if $G$ is either a free product with amalgamation $A\underset{C}{*}B$ or an HNN-extension $G=A\underset{C}{*}\left(t\right)$. We invoke Bass–Serre theory to classify all infinite groups which admit cubic Cayley graphs of connectivity two in terms of splittings over a subgroup.

Classification : 05C10, 05C63, 20E06, 20F65
Mots clés : Free product with amalgamation, HNN-extension, Bass–Serre theory, planar graphs.

[1] Babai, László 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

[2] Carmesin, Johannes; Diestel, Reinhard; Hamann, Matthias; Hundertmark, Fabian Canonical tree-decompositions of finite graphs I. Existence and algorithms, J. Combin. Theory Ser. B, Volume 116 (2016), pp. 1-24 | DOI | MR | Zbl

[3] Carmesin, Johannes; Diestel, Reinhard; Hundertmark, Fabian; Stein, Maya Connectivity and tree structure in finite graphs, Combinatorica, Volume 34 (2014) no. 1, pp. 11-45 | DOI | MR | Zbl

[4] Carmesin, Johannes; Diestel, Reinhard; Miraftab, Babak Canonical trees of tree-decompositions (2020) (https://arxiv.org/pdf/2002.12030.pdf)

[5] Diestel, Reinhard Locally finite graphs with ends: a topological approach, II. Applications, Discrete Math., Volume 310 (2010) no. 20, pp. 2750-2765 | DOI | MR | Zbl

[6] Diestel, Reinhard Locally finite graphs with ends: a topological approach, Discrete Math., Volume 310–312 (2010–11), p. 2750-2765 (310); 1423–1447 (311); 21–29 (312) (arXiv:0912.4213)

[7] Diestel, Reinhard Graph theory, Graduate Texts in Mathematics, 173, Springer, Berlin, 2017, xviii+428 pages | DOI | MR

[8] Droms, Carl; Servatius, Brigitte; Servatius, Herman Connectivity and planarity of Cayley graphs, Beiträge Algebra Geom., Volume 39 (1998) no. 2, pp. 269-282 | MR

[9] Georgakopoulos, Agelos Characterising planar Cayley graphs and Cayley complexes in terms of group presentations, European J. Combin., Volume 36 (2014), pp. 282-293 | DOI | MR | Zbl

[10] Georgakopoulos, Agelos The planar cubic Cayley graphs of connectivity 2, European J. Combin., Volume 64 (2017), pp. 152-169 | DOI | MR | Zbl

[11] Hamann, Matthias Planar transitive graphs, Electron. J. Combin., Volume 25 (2018) no. 4, Paper No. 4.8, 18 pages | MR

[12] Hamann, Matthias; Lehner, Florian; Miraftab, Babak; Rühmann, Tim A Stallings’ type theorem for quasi-transitive graphs (2018) (https://arxiv.org/pdf/1812.06312.pdf)

[13] Jung, Heinz A.; Watkins, Mark E. On the structure of infinite vertex-transitive graphs, Discrete Math., Volume 18 (1977) no. 1, pp. 45-53 | DOI | MR | Zbl

[14] Maschke, H. The Representation of Finite Groups, Especially of the Rotation Groups of the Regular Bodies of Three-and Four-Dimensional Space, by Cayley’s Color Diagrams, Amer. J. Math., Volume 18 (1896) no. 2, pp. 156-194 | DOI | MR | Zbl

[15] Richter, R. Bruce Decomposing infinite 2-connected graphs into 3-connected components, Electron. J. Combin., Volume 11 (2004) no. 1, Research Paper 25, 10 pages | MR | Zbl

[16] Serre, Jean-Pierre Trees, Springer-Verlag, Berlin-New York, 1980, ix+142 pages | MR

[17] Tutte, William T. Connectivity in graphs, Mathematical Expositions, University of Toronto Press, Toronto, Ont.; Oxford University Press, London, 1966 no. 15, ix+145 pages | MR | Zbl

[18] Watkins, Mark E. Les graphes de Cayley de connectivité un, Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976) (Colloq. Internat. CNRS), Volume 260, CNRS, Paris, 1978, pp. 419-422 | MR

[19] Zieschang, Heiner; Vogt, Elmar; Coldewey, Hans-Dieter Surfaces and planar discontinuous groups, Lecture Notes in Mathematics, 835, Springer, Berlin, 1980, x+334 pages | MR