Tilings of the torus and the Klein bottle and vertex-transitive graphs on a fixed surface

Author:
Carsten Thomassen

Journal:
Trans. Amer. Math. Soc. **323** (1991), 605-635

MSC:
Primary 57Q99; Secondary 05C10, 05C25

DOI:
https://doi.org/10.1090/S0002-9947-1991-1040045-3

MathSciNet review:
1040045

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We describe all regular tilings of the torus and the Klein bottle. We apply this to describe, for each orientable (respectively nonorientable) surface , all (but finitely many) vertex-transitive graphs which can be drawn on but not on any surface of smaller genus (respectively crosscap number). In particular, we prove the conjecture of Babai that, for each , there are only finitely many vertex-transitive graphs of genus . In fact, they all have order . The weaker conjecture for Cayley graphs was made by Gross and Tucker and extends Hurwitz' theorem that, for each , there are only finitely many groups that act on the surface of genus . We also derive a nonorientable version of Hurwitz' theorem.

**[1]**A. Altschuler,*Construction and enumeration of regular maps on the torus*, Discrete Math.**4**(1973), 201-217. MR**0321797 (48:164)****[2]**J. Battle, F. Harary, Y. Kodama, and J. W. T. Youngs,*Additivity of the genus of a graph*, Bull. Amer. Math. Soc.**68**(1962), 565-568. MR**0155313 (27:5247)****[3]**H. Fleischner and W. Imrich,*Transitive planar graphs*, Math. Slovaca**29**(1979), 97-106. MR**578282 (81f:05093)****[4]**J. L. Gross and T. W. Tucker,*Topological graph theory*, Wiley, New York, 1987. MR**898434 (88h:05034)****[5]**B. Grünbaum and G. C. Shephard,*Tilings and patterns*, Freeman, New York, 1987. MR**857454 (88k:52018)****[6]**S. Stahl and L. W. Beineke,*Blocks and the nonorientable genus of a graph*, J. Graph Theory**1**(1977), 75-78. MR**0460165 (57:161)****[7]**C. Thomassen,*Embeddings of graphs with no short noncontractible cycles*, J. Combin. Theory Ser. B**48**(1990), 155-177. MR**1046752 (91b:05069)****[8]**-,*Embeddings and minors*, in Handbook of Combinatorics (M. Grötschel, L. Lovász, and R. L. Graham, eds.), North-Holland (to appear). MR**831711****[9]**-,*The graph genus problem is*-*complete*, J. Algorithms**10**(1989), 568-576. MR**1022112 (91d:68054)****[10]**-,*The Jordan-Schönflies theorem and the classification of surfaces*, Amer. Math. Monthly (to appear). MR**1144352 (92k:57026)****[11]**T. W. Tucker,*Finite groups acting on surfaces and the genus of a group*, J. Combin. Theory Ser. B**34**(1983), 82-98. MR**701174 (85b:20055)****[12]**W. T. Tutte,*Connectivity in graphs*, Univ. of Toronto Press, Toronto, 1966.**[13]**L. Babai,*Vertex-transitive graphs and vertex-transitive maps*, J. Graph Theory (to appear). MR**1133814 (92m:05064)**

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC:
57Q99,
05C10,
05C25

Retrieve articles in all journals with MSC: 57Q99, 05C10, 05C25

Additional Information

DOI:
https://doi.org/10.1090/S0002-9947-1991-1040045-3

Article copyright:
© Copyright 1991
American Mathematical Society