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

MathSciNet review:
1040045

Full-text PDF Free Access

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]**Amos Altshuler,*Construction and enumeration of regular maps on the torus*, Discrete Math.**4**(1973), 201–217. MR**0321797****[2]**Joseph Battle, Frank Harary, Yukihiro Kodama, and J. W. T. Youngs,*Additivity of the genus of a graph*, Bull. Amer. Math. Soc.**68**(1962), 565–568. MR**0155313**, 10.1090/S0002-9904-1962-10847-7**[3]**Herbert Fleischner and Wilfried Imrich,*Transitive planar graphs*, Math. Slovaca**29**(1979), no. 2, 97–106 (English, with Russian summary). MR**578282****[4]**Jonathan L. Gross and Thomas W. Tucker,*Topological graph theory*, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1987. A Wiley-Interscience Publication. MR**898434****[5]**Branko Grünbaum and G. C. Shephard,*Tilings and patterns*, W. H. Freeman and Company, New York, 1987. MR**857454****[6]**Saul Stahl and Lowell W. Beineke,*Blocks and the nonorientable genus of graphs*, J. Graph Theory**1**(1977), no. 1, 75–78. MR**0460165****[7]**Carsten Thomassen,*Embeddings of graphs with no short noncontractible cycles*, J. Combin. Theory Ser. B**48**(1990), no. 2, 155–177. MR**1046752**, 10.1016/0095-8956(90)90115-G**[8]**Lajos Takács,*Combinatorics*, Nonparametric methods, Handbook of Statist., vol. 4, North-Holland, Amsterdam, 1984, pp. 123–143. MR**831711**, 10.1016/S0169-7161(84)04009-8**[9]**Carsten Thomassen,*The graph genus problem is NP-complete*, J. Algorithms**10**(1989), no. 4, 568–576. MR**1022112**, 10.1016/0196-6774(89)90006-0**[10]**Carsten Thomassen,*The Jordan-Schönflies theorem and the classification of surfaces*, Amer. Math. Monthly**99**(1992), no. 2, 116–130. MR**1144352**, 10.2307/2324180**[11]**Thomas W. Tucker,*Finite groups acting on surfaces and the genus of a group*, J. Combin. Theory Ser. B**34**(1983), no. 1, 82–98. MR**701174**, 10.1016/0095-8956(83)90009-6**[12]**W. T. Tutte,*Connectivity in graphs*, Univ. of Toronto Press, Toronto, 1966.**[13]**László Babai,*Vertex-transitive graphs and vertex-transitive maps*, J. Graph Theory**15**(1991), no. 6, 587–627. MR**1133814**, 10.1002/jgt.3190150605

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:
http://dx.doi.org/10.1090/S0002-9947-1991-1040045-3

Article copyright:
© Copyright 1991
American Mathematical Society