Tilings of the torus and the Klein bottle and vertex-transitive graphs on a fixed surface
HTML articles powered by AMS MathViewer
- by Carsten Thomassen PDF
- Trans. Amer. Math. Soc. 323 (1991), 605-635 Request permission
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
- Amos Altshuler, Construction and enumeration of regular maps on the torus, Discrete Math. 4 (1973), 201–217. MR 321797, DOI 10.1016/S0012-365X(73)80002-0
- 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 155313, DOI 10.1090/S0002-9904-1962-10847-7
- Herbert Fleischner and Wilfried Imrich, Transitive planar graphs, Math. Slovaca 29 (1979), no. 2, 97–106 (English, with Russian summary). MR 578282
- 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
- Branko Grünbaum and G. C. Shephard, Tilings and patterns, W. H. Freeman and Company, New York, 1987. MR 857454
- Saul Stahl and Lowell W. Beineke, Blocks and the nonorientable genus of graphs, J. Graph Theory 1 (1977), no. 1, 75–78. MR 460165, DOI 10.1002/jgt.3190010114
- Carsten Thomassen, Embeddings of graphs with no short noncontractible cycles, J. Combin. Theory Ser. B 48 (1990), no. 2, 155–177. MR 1046752, DOI 10.1016/0095-8956(90)90115-G
- Lajos Takács, Combinatorics, Nonparametric methods, Handbook of Statist., vol. 4, North-Holland, Amsterdam, 1984, pp. 123–143. MR 831711, DOI 10.1016/S0169-7161(84)04009-8
- Carsten Thomassen, The graph genus problem is NP-complete, J. Algorithms 10 (1989), no. 4, 568–576. MR 1022112, DOI 10.1016/0196-6774(89)90006-0
- Carsten Thomassen, The Jordan-Schönflies theorem and the classification of surfaces, Amer. Math. Monthly 99 (1992), no. 2, 116–130. MR 1144352, DOI 10.2307/2324180
- 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, DOI 10.1016/0095-8956(83)90009-6 W. T. Tutte, Connectivity in graphs, Univ. of Toronto Press, Toronto, 1966.
- László Babai, Vertex-transitive graphs and vertex-transitive maps, J. Graph Theory 15 (1991), no. 6, 587–627. MR 1133814, DOI 10.1002/jgt.3190150605
Additional Information
- © Copyright 1991 American Mathematical Society
- 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