Vertex‐transitive graphs and vertex‐transitive maps
Author:
- 1 December 1991
- journal article
- research article
- Published by Wiley in Journal of Graph Theory
- Vol. 15 (6) , 587-627
Abstract
We consider vertex‐transitive graphs embeddable on a fixed surface. We prove that all but a finite number of them admit embeddings as vertex‐transitive maps on surfaces of nonnegative Euler characteristic (sphere, projective plane, torus, or Klein bottle). It follows that with the exception of the cycles and a finite number of additional graphs, they are factor graphs of semiregular plane tilings. The results generalize previous work on the genus of minimal Cayley graphs by V. Proulx and T. W. Tucker and were obtained independently by C. Thomassen, with significant differences in the methods used. Our method is based on an excursion into the infinite. The local structure of our finite graphs is studied via a pointwise limit construction, and the infinite vertex‐transitive graphs obtained as such limits are classified by their connectivity and the number of ends. In two appendices, we derive a combinatorial version of Hurwitz's Theorem, and classify the vertex‐transitive maps on the Klein bottle.Keywords
This publication has 19 references indexed in Scilit:
- Connectivity of infinite graphs having a transitive torsion group actionArchiv der Mathematik, 1980
- The Number of Groups of a given GenusTransactions of the American Mathematical Society, 1980
- The number of groups of a given genusTransactions of the American Mathematical Society, 1980
- Classification of the toroidal groupsJournal of Graph Theory, 1978
- Blocks and the nonorientable genus of graphsJournal of Graph Theory, 1977
- Groups of graphs on given surfacesActa Mathematica Hungarica, 1973
- Eine Eigenschaft der Atome endlicher GraphenArchiv der Mathematik, 1971
- Homomorphies tze f r GraphenMathematische Annalen, 1968
- Homomorphieeigenschaften und mittlere Kantendichte von GraphenMathematische Annalen, 1967
- The Representation of Finite Groups, Especially of the Rotation Groups of the Regular Bodies of Three-and Four-Dimensional Space, by Cayley's Color DiagramsAmerican Journal of Mathematics, 1896