Tilings of the torus and the Klein bottle and vertex-transitive graphs on a fixed surface. (English) Zbl 0722.05031

This beautiful paper is concerned with the problem of constructing and enumerating all possible regular tilings on a surface. The author describes all regular tilings of the torus and the Klein bottle. As a consequence, it can be described, for each orientable (resp. nonorientable) surface S, all (but finitely many) vertex-transitive graphs which can be drawn on S but not on any surface of smaller genus (resp. crosscap number). In particular, it is proved the conjecture of Babai that, for each \(g\geq 3\), there are only finitely many vertex- transitive graphs of genus g [see J. L. Gross and T. W. Tucker, Topological Graph Theory (1987; Zbl 0621.05013)]. Indeed, they all have order \(<10^{10}g\). T. W. Tucker [J. Comb. Theory, Ser. B 34, 82-98 (1983; Zbl 0521.05027)] proved that, if a finite group acts on a surface S, then some Cayley graph G of the group has a 2-cell embedding on S such that every homeomorphism in the group induces an isomorphism. The results of the present paper tell what the graph G is, provided the group is large. Thus the author can obtain an alternative description of all (but finitely many) finite homeomorphism groups of a surface (compare also the Hurwitz theorem). In particular, it follows that \(S_ 0\), \(S_ 1\), \(N_ 1\), \(N_ 2\) are the only surfaces having infinitely many homeomorphism groups. Here \(S_ g\) and \(N_ k\) denote the orientable (resp. nonorientable) surface of genus g (resp. crosscap number k).


05C10 Planar graphs; geometric and topological aspects of graph theory
57M15 Relations of low-dimensional topology with graph theory
57S25 Groups acting on specific manifolds
Full Text: DOI


[1] Amos Altshuler, Construction and enumeration of regular maps on the torus, Discrete Math. 4 (1973), 201 – 217. · Zbl 0253.05117 · doi:10.1016/S0012-365X(73)80002-0
[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. · Zbl 0142.41501
[3] Herbert Fleischner and Wilfried Imrich, Transitive planar graphs, Math. Slovaca 29 (1979), no. 2, 97 – 106 (English, with Russian summary). · Zbl 0439.05026
[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. · Zbl 0621.05013
[5] Branko Grünbaum and G. C. Shephard, Tilings and patterns, W. H. Freeman and Company, New York, 1987. · Zbl 0601.05001
[6] Saul Stahl and Lowell W. Beineke, Blocks and the nonorientable genus of graphs, J. Graph Theory 1 (1977), no. 1, 75 – 78. · Zbl 0366.05030 · doi:10.1002/jgt.3190010114
[7] Carsten Thomassen, Embeddings of graphs with no short noncontractible cycles, J. Combin. Theory Ser. B 48 (1990), no. 2, 155 – 177. · Zbl 0704.05011 · doi: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. · Zbl 0598.62056 · doi: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. · Zbl 0689.68071 · doi: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. · Zbl 0773.57001 · doi: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. · Zbl 0521.05027 · doi:10.1016/0095-8956(83)90009-6
[12] W. T. Tutte, Connectivity in graphs, Univ. of Toronto Press, Toronto, 1966. · Zbl 0146.45603
[13] László Babai, Vertex-transitive graphs and vertex-transitive maps, J. Graph Theory 15 (1991), no. 6, 587 – 627. · Zbl 0743.05020 · doi:10.1002/jgt.3190150605
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.