Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



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

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 $ S$, all (but finitely many) vertex-transitive graphs which can be drawn on $ S$ but not on any surface of smaller genus (respectively crosscap number). In particular, we prove the conjecture of Babai that, for each $ g \geqslant 3$, there are only finitely many vertex-transitive graphs of genus $ g$. In fact, they all have order $ < {10^{10}}g$. The weaker conjecture for Cayley graphs was made by Gross and Tucker and extends Hurwitz' theorem that, for each $ g \geqslant 2$, there are only finitely many groups that act on the surface of genus $ g$. We also derive a nonorientable version of Hurwitz' theorem.

References [Enhancements On Off] (What's this?)

  • [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 $ NP$-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)

Similar Articles

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

Article copyright: © Copyright 1991 American Mathematical Society

American Mathematical Society