Some Semi - Equivelar Maps Ashish K. Upadhyay, Anand K. Tiwari and Dipendu Maity 1 Department of Mathematics 1 0 Indian Institute of Technology Patna 2 Patliputra Colony, Patna – 800013, India n upadhyay, anand, dipendumaity @iitp.ac.in a { } J January 18, 2011 7 1 ] T G Abstract . h Semi-Equivelar maps are generalizations of Archimedean Solids (as are equivelar maps of t a thePlatonicsolids)tothesurfacesotherthan2 Sphere. Weclassifysomesemiequivelarmaps − m on surface of Euler characteristic 1 and show that none of these are vertex transitive. We − [ establish existence of 12-covered triangulations for this surface. We further construct double cover of these maps to show existence of semi-equivelar maps on the surface of double torus. 2 We also construct severalsemi-equivelarmaps on the surfaces of Euler characteristics 8 and v − 1 10 and on non-orientable surface of Euler characteristics 2. − − 7 6 0 AMS Subject Classification: 57M10, 57M20, 52B50, 52B70, 52C20 1. Keywords: Semi-Equivelar Maps, d-Covered Triangulations, Equivelar Triangulations. 0 1 1 1 Introduction and results : v Xi As is well known, equivelar triangulations, also known as degree regular triangulations of surfaces and in more generality equivelar maps on surfaces are generalizations of the maps on surfaces of r a five Platonic solids to the surfaces other than sphere. Here we attempt to study generalizations of Archimedean solids to some surfaces of negative Euler characteristics. Their study for the surfaces of non-negative Euler characteristics has been carried out in [13]. We call such objects as Semi-Equivelar Maps or SEM(s). The following definitions are given in [3] and we reproduce it here for the sake of completeness and ready reference. A p-Cycle, denoted C , is a finite connected 2-regular graph with p vertices. p A 2-dimensional Polyhedral Complex K is a collection of p -cycles, where p : 1 i n is a set i i { ≤ ≤ } of positive integers 3, together with vertices and edges in the cycles such that the intersection ≥ of any two cycles is empty, a vertex or is an edge. The cycles are called faces of K. The symbols V(K) and EG(K) respectively denote the set of vertices and edges of K. A polyhedral complex K is called a Polyhedral 2-manifold if for each vertex v the faces containing v are of the form C ,...,C where C C ,...C C , and C C are edges for some m 3. A p1 pm p1 ∩ p2 pm−1 ∩ pm pm ∩ p1 ≥ connected finite polyhedral 2-manifold is called a Polyhedral Map. We will use the term map for a polyhedral map. 1 We associate a geometric object K to a polyhedral complex K as follows: corresponding to | | each p-cycle C in K, consider a p-gon D whose boundary cycle is C . Then K is union of p p p | | all such p-gons and is called the geometric carrier of K. The complex K is said to be connected (resp. orientable) if K is connected (resp. orientable) topological space. Between any two | | polyhedral complexes K and K we define an isomorphism to be a map f: K K such 1 2 1 2 −→ that f : V(K ) V(K ) is a bijection and f(σ) is a cell in K if and only if σ is a cell |V(K1) 1 −→ 2 2 in K . If K = K then f is called an automorphism of K . The set of all automorphisms of 1 1 2 1 a polyhedral complex K form a group under the operation composition of maps. This group is called the group of automorphisms of K. If this group acts transitively on the set V(K) then the complex is called a vertex transitive complex. Some vertex transitive maps of Euler characteristic 0 have been studied in [2]. The Face sequence of a vertex v in a map, see figure in Example 8, is a finite sequence (ap,bq,....,mr) of powers of positive integers a,b,...,m 3 and p,q,...,r 1, such that through ≥ ≥ the vertex v, p numbers of C , q numbers of C , ..., r numbers of C are incidents. A map K a b m is said to be Semi-Equivelar if face sequence of each vertex of K is same. Thus, for example the face sequence of a vertex in the maps of Example 7 is (35,4). In [13], maps with face sequence (33,42) and (32,4,3,4) have been considered. A triangulation of a connected closed surface is called Equivelar (or degree regular) if each of its vertices have the same degree. Thus a d equivelar triangulation is a SEM of type (3d). − A triangulation is called d-covered if each edge of the triangulation is incident with a vertex of degree d. In articles [4] and [5] equivelar triangulations have been studied for Euler characteristics 0 and -2. In [11] Negami and Nakamoto studied d-covered triangulations and asked the question about existence of such triangulations on a surface of Euler charateristic χ with the condition 5+√49 24χ that d = 2 − see also [12]. In the articles [9] questions about existence of such ⌊ 2 ⌋ χd triangulations for 2 χ 127 and whenever n = is an integer is considered. There, − ≤ ≤ − d 6 use of equivelar triangulations of surfaces to construct th−e required d-covered triangulations has been made. It is well known that the equivelar triangulations do not exist for surface of Euler characteristic 1 and some study about maps on this surface has been made in [1]. The current − workismotivated byanattempt tosearch forexistenceof12-covered triangulations onthesurface of Euler characteristic 1. We answer the question in affirmative. We construct and classify − some semi equivelar maps on this surface. A glance at the Euler’s formula χ = no.of vertices - no.of edges + no.offaces , indicates that at each vertex, if we allow one of the faces to be a quadrangle and choose smallest possible number of triangles in such a way that curvature is negative thenitmightbepossibletohave somemapsonthis surface. Suchamapis anexampleof what we defined to be a Semi-Equivelar map on a surface. In current work, we allowed one square and five triangles at each vertex to discover that if N denotes number of vertices, the Euler’s equation gives χ = N(−1). Thus if we take N = 12 then we may obtain a SEM of type (35,4) on 12 the non - orientable surface of Euler characteristic 1. In the following lines we will be defining − a procedure to add handles to a SEM. This process is not new and appeared earlier in [10]. Let C (v ,v ,...,v ) and Z (u ,u ,...,u ) denote cycles of length l. We define a cylinder l 1 2 l l 1 2 l C (C ,Z )withboundarycomponentsC andZ tobethecomplexwithvertexset v ,v ,...,v ,u , ll l l l l 1 2 l 1 { u ,...,u and facets v v u u ,v v u u ,...,v v u u . If K denotes a SEM of type (35,4), 2 l} { 1 2 i2 i1 2 3 i3 i2 1 l il i1} it is possible to add a cylinder to K to obtain another map as follows: let Q and Q denote two 1 2 quadrangularfacets of K such thatV(Q ) V(Q ) =. Remove theinterior ofQ and Q toobtain 1 2 1 2 ∩ 2 two disjoint cycles ∂(Q ) and ∂(Q ) of length four as boundary components of K. One may now 1 2 plug in a cylinder C (∂(Q ),∂(Q )) by identifying the boundaries. If one is careful in choosing 44 1 2 pairs (Q ,Q ) so as to preserve a semi-equivelar type for K, we do obtain a genuine map from K. 1 2 One can see that by this the Euler characteristic is increased by 2. It is sometimes needed to − triangulate the cylinder suitably (so as to retain the semi-equivelar type) and obtain an addition of triangular facets instead of quadrangular faces. We perform two types of cylinder addition (i) we adjoin a cylinder to the boundary components of K Q ,Q , or (ii) we adjoin a cylinder in 1 2 \{ } the boundary of K Q SL Q for two SEMs K,L such that Q K and Q L. We use both 1 2 1 2 \ \ ∈ ∈ these types of cylinder additions to obtain SEM of types 35,42 and 37,4 on surfaces of Euler { } { } characteristics 8 and 10, see Examples 11 and 13. − − Let EG(K) be the edge graph of a map K and V(K) = v ,v ,...,v . Let L (v ) = v 1 2 n K i j { } { ∈ V(K): v v EG(K) . For 0 t n we define a graph G (K) with V(G (K)) = V(K) and i j t t ∈ } ≤ ≤ v v EG(G (K)) if L (v )TL (v ) = t, in other words the number of elements in the set i j t K i K j ∈ | | ′ L (v )TL (v ) is t. This graph was introduced in [5] by B. Datta. Moreover if K and K are K i K j ′ two isomorphic maps then G (K) = G (K ) for each i. For computations, we have used GAP [8]. i ∼ i We have also computed reduced homology groups of the objects using [7]. We classify all the semi-equivelar maps of type (35,4) on the surface of Euler characteristics -1 and show that there are precisely three such objects up to isomorphism. In other words we show that : Theorem : 1 If K is a semi equivelar maps of type (35,4) on the surface of Euler characteristic 1 then K is isomorphic to one of K , K or K given in Example 7. 1 2 3 − Corollary : 2 There exists a 12-covered triangulation of the surface of Euler characteristics 1. − Proof : To each face of the map add the barycenter and join each vertices of the face with this newly introduced vertex. This process is called stacking a face, see [9]. The proof now follows by stacking each face of the (35,4) SEM on the surfaces of Euler characteristic 1. The resulting − triangulation is 12-covered. 2 In [6], Karabas and Nedela have presented a census of vertex transitive Archimedean solids of genus two. This census includes one SEM of type (35,4) on the surface of double torus on 24 vertices. Here we construct more such maps on the orientable surface of genus two as double covers of the SEMs of same type on surface of Euler characteristic 1. For each of these maps − we present their double covers in Example 2 which turn out to be mutually non - isomorphic. We prove that: Theorem : 3 There exist at least four SEM of type (35,4) on the surface of Euler characteristic 2. Three of these is orientable and one is non orientable. None of these maps are vertex − transitive. Corollary : 4 There are at least five SEMs of type (35,4) on the surface of Euler characteristic 2. Four of these are orientable and one is non-orientable. Among the orientable SEMs one is − vertex transitive and the remaining are not. 2 We further show the following: Theorem : 5 There exist at least 10 SEMs of types (35,42) on the surface of Euler characteristic 8. Two of these are orientable and remaining are non - orientable. − Theorem : 6 There exist at least 11 SEMs of types (37,4) on the surface of Euler characteristic 10. Two of these are orientable and remaining are non - orientable. − 3 2 Examples Example : 7 Some Semi Equivelar Maps on surface of Euler Characteristics -1: K1 = 012, 017, 045, 056, 067, 128, 158, 15u, 236, 267, 278, 34v, 369, 39u, 3uv, 45u, 49u, 49v, { 78v, 89v, 0234, 17vu, 5698 } K2 = 012, 017, 045, 056, 067, 129, 17v, 189, 238, 268, 269, 34v, 389, 39u, 3uv, 45u, 47u, 47v, { 568, 5uv, 0234, 185v, 67u9 } K3 = 012, 017, 045, 056, 067, 129, 178, 19v, 238, 268, 269, 34v, 378, 37u, 3uv, 45u, 49u, 49v, { 568, 5uv, 0234, 85v1, 67u9 } The Graphs EG(G (K )) = , EG(G (K )) = [2,4],[7,10] . EG(G (K )) = [2,4],[3,12] 6 1 2 1 2 2 ∅ { } { } and EG(G (K )) = [1,6],[5,7] . Also, EG(G (K )) = and EG(G (K )) = [1,6],[8,12] . 6 2 2 3 6 3 { } ∅ { } Therefore, K = K , K = K and K = K . A look at these graphs one can easily deduce that 1 6∼ 2 1 6∼ 3 2 6∼ 3 K , K and K are not vertex transitive. 1 2 3 Example : 8 (a) Some face sequences of vertex v = 0 3 2 3 2 (cid:0) (cid:2)@ 3 2 4(cid:0)HH(cid:0)HH(cid:8)H(cid:8)(cid:8)H(cid:2)(cid:2)(cid:2)(cid:8)(cid:2) (cid:8)@(cid:8)(cid:8)@1 4(cid:0)H(cid:0)H(cid:0)HBHBHBBB(cid:8)(cid:2)(cid:2)(cid:2)(cid:8)(cid:2)(cid:2)@(cid:8)@(cid:8)(cid:8)@1 4(cid:0)@(cid:0)(cid:0)@@@(cid:0)(cid:0)@0 (cid:0)(cid:0)@1@@(cid:0) 7 (cid:8)(cid:8) 0 HH @ (cid:0) @ (cid:0) 7H(cid:8) H(cid:8)H(cid:8)7 0 @5(cid:0) @(cid:0)6 HHHH(cid:8)(cid:8)(cid:8) 7HHH (cid:8)(cid:8)(cid:8)(cid:8)7 HH(cid:8) 6 6 Type :(32,4,3,4) Type :(35,4) Type :(33,42) (b) Figure showing two types of Cylinders: v3 v4 v1 v2 u3 u4 u1 u2 u2 u5 v5 v2 u1 u6 u3 v1 v6 C66(v1...v6,u1...u6) v3 C33(v1v2v3,u1u2u3) Example : 9 (35,4)-SEM on the double torus. These example are constructed by lifting the SEMs K to its double cover T , i.e., the double torus. Consider a map defined by φ 0,12 = a; i i { } φ 1,18 = b; φ 2,20 = c; φ 3,21 = d; φ 4,19 = e; φ 5,13 = f; φ 6,23 = g; φ 7,17 = h; { } { } { } { } { } { } { } φ 8,18 = i; φ 9,15 = j; φ 10,14 = k; φ 11,22 = l and the map ψ: a 0,b 1,...,l { } { } { } { } { 7→ 7→ 7→ 11 . We see that ψ φ: T K , i = 1,2,3 is a covering. Clearly it is a two fold orientable i i } ◦ −→ covering: 4 T1 := [0, 1, 2], [0, 1, 7], [0, 6, 7], [0, 6, 13], [0, 4, 13], [1, 2, 8], [1, 5, 8], [1, 5, 10], [2, 7, 8], [2, 6, { 7], [2, 3, 6],[3, 6, 9], [3, 9, 10], [3, 10, 22], [3, 4, 22], [4, 22, 15], [4, 15, 14], [4, 14, 13], [5, 10, 19], [5, 19, 12], [5, 12, 23], [7, 8, 22], [8, 15, 22], [9, 10, 19], [9, 11, 16], [9, 11, 19], [11, 16, 17], [11, 19, 21], [11, 14, 21], [12, 17, 23], [12, 17, 18], [12, 18, 20], [13, 14, 18], [13, 16, 18], [14, 15, 21], [15, 21, 23], [16, 17, 20], [16, 18, 20], [17, 20, 23], [20, 21, 23] S [0, 2, 3, 4], [1, 7, 22, 10], [5, 8, 15, } { 23], [6, 9, 16, 13], [11, 14, 18, 17], [12, 19, 21, 20] } T2 := [0, 2, 13], [0, 13, 7], [0, 6, 7], [0, 5, 6], [0, 4, 5], [1, 8, 9], [1, 9, 14], [1, 12, 14], [1, 12, 19], { [1, 11, 19], [2, 3, 8], [2, 6, 8], [2, 6, 21], [2, 13, 21], [3, 8, 9], [3, 9, 22], [3, 22, 23], [3, 4, 23], [4, 5, 10], [4, 7, 10], [4, 7, 23], [5, 6, 8], [5, 10, 11], [7, 13, 23], [9, 14, 18], [10, 11, 15], [10, 15, 21], [11, 15, 16], [11, 16, 19], [12, 18, 19], [12, 17, 18], [12, 16, 17], [13, 20, 21], [14, 15, 20], [14, 18, 20], [15, 20, 21], [16, 17, 22], [16, 19, 22], [17, 18, 20], [17, 22, 23] S [0, 2, 3, 4], [1, 8, 5, 11], [6, 7, } { 10, 21], [9, 18, 19, 22], [12, 14, 15, 16], [13, 20, 17, 23] } T3 := [0, 1, 2], [0, 1, 7], [0, 6, 7], [0, 5, 6], [0, 4, 5], [1, 2, 9], [1, 9, 11], [1, 7, 8], [2, 3, 8], [2, 6, 8], { [2, 6, 9], [3, 7, 8], [3, 7, 10], [3, 10, 23], [3, 4, 23], [4, 5, 22], [4, 21, 22], [4, 21, 23], [5, 6, 8], [5, 11, 22], [9, 11, 16], [9, 10, 16], [10, 11, 17], [10, 16, 17], [11, 15, 16], [11, 15, 22], [12, 16, 17], [12, 17, 18], [12, 18, 19], [12, 13, 19], [12, 13, 14], [13, 14, 21], [13, 21, 23], [13, 19, 20], [14, 18, 20], [14, 18, 21], [14, 15, 20], [15, 19, 22], [15, 19, 20], [17, 18, 20] S [0, 2, 3, 4], [1, 8, 5, 11], [6, 7, 10, 9], } { [12, 14, 15, 16], [13, 20, 17, 23], [18, 19, 22, 21] } Example : 10 Following is the example of a SEM of type (35,4) on a non - orientable surface of Euler characteristics 2: − N := [0, 1, 2], [0, 1, 18], [0, 18, 14], [0, 14, 15], [0, 15, 4],[1, 2, 8],[1, 8, 5], [1, 5, 10], [2, 3, 6], [2, { 6, 7], [2, 7, 8], [3, 6, 13], [3, 10, 13], [3, 10, 11],[3, 4, 11], [4, 11, 9], [4, 9, 16], [4, 15, 16], [5, 1, 8], [5, 10, 17], [5, 17, 23], [5, 6, 23], [6, 7, 23], [7, 8, 12], [7, 22, 23], [8, 12, 13], [9, 11, 19], [9, 16, 21], [9, 14, 21], [10, 13, 17], [12, 13, 17], [12, 17, 21], [12, 21, 16], [14, 18, 20], [14, 20, 21], [15, 16, 22], [15, 19, 22], [18, 19, 20], [18, 11, 19], [19, 20, 22], [20, 22, 23], [0, 2, 3, 4], [1, 10, 11, 18], [5, 6, 13, 8], [7, 12, 16, 22], [9, 14, 15, 19], [17, 21, 20, 23] } Example : 11 In the Table 1 some SEMs of type (35,42) and (37,4) on the surfaces of Euler characteristic 8 and 10 are presented. These examples are obtained from K s by cylinder i − − addition techniques. The last column in the tables gives the faces where cylinders are added. The notation K (k,l) denotes lth example in the set of objects obtained by adding quadrangle for k = 1 ij and triangle for k = 2 between K and K . i j Lemma : 12 The maps defined in the Example 11 above are all non - isomorphic. Proof : Consider the enumeration of edges in G , G and G of the SEMs in this example 1 5 6 presented in tabular form above. From this it is immediate that the SEMs of this example are all non-isomorphic. 2 Example : 13 Table 2 presents some SEM which are obtained by adding cylinders in the double covers T , T and T . The notation T (j,k) denotes the kth object obtained from the double torus 1 2 3 i T of example 9, by adding the cylinders of type C for j = 1 and of type C for j = 2. The last i 44 33 column in the tables gives the faces where cylinders are added. 5 Table 1: Table representing cylinder additions to K s ij Maps #1 #5 #6 χ Or. Handle Type K11(1,1) 0 10 4 -8 NO C44([0, 2, 3, 4],[18, 21, 19, 20]), C44([1, 7, 11, 10], [16, 23, 13, 12]), C44([5, 6, 9, 8], [14, 15, 22, 17]) K11(2,1) 26 36 2 -10 NO C33([0, 1, 2], [12, 13, 14]), C33([ 3, 6, 9 ], [15, 18, 21]) C33([ 4, 5, 10 ], [16, 17, 22]), C33([ 7, 8, 11 ], [19, 20, 23]) K22(1,1) 0 12 0 -8 NO C44([0, 2, 3, 4], [12, 14, 15, 16]), C44([1, 8, 5, 11], [13, 20, 17, 23]), C44([6, 9, 10, 7], [21, 18, 19, 22]) K22(2,1) 16 32 4 -10 NO C33([0, 1, 2], [12, 13, 14]), C33([ 3, 9, 10 ], [15, 21, 22]), C33([ 4, 7, 11 ], [16, 19, 23]), C33([ 5, 6, 8 ], [17, 18, 20]) K33(1,1) 0 16 0 -8 NO C44([0, 2, 3, 4], [12, 14, 15, 16]), C44([6, 7, 10, 9], [19, 22, 21, 18]), C44([1, 11, 5, 8], [13, 23, 17, 20]) K33(2,1) 18 34 6 -10 NO C33([0, 1, 2], [12, 13, 14]), C33([ 3, 7, 10 ], [15, 19, 22]), C33([ 4, 9, 11 ], [16, 21, 23]),C33([ 5, 6, 8 ], [17, 18, 20]) K12(1,1) 1 10 2 -8 NO C33([0, 2, 3, 4], [13, 14, 15, 23]), C33([1, 7, 11, 10], [19, 16, 22, 12]), C33([5, 8, 9, 6], [17, 18, 21, 20]) K12(2,1) 19 34 3 -10 NO C33([0, 1, 2 ], [ 12, 13, 14]), C33([3, 6, 9 ], [ 15, 21, 22 ]), C33([ 4, 5, 10 ], [ 16, 19, 23 ]), C33([ 7, 8, 11 ], [ 17, 18, 20 ]) K13(1,1) 1 15 2 -8 NO C44([0, 2, 3, 4], [12, 14, 15, 16]), C44([1, 7, 11, 10], [13, 23, 17, 20]), C44([5, 8, 9, 6], [18, 19, 22, 21]) K13(2,1) 21 35 4 -10 NO C33([0, 1, 2], [ 12, 13, 14]), C33([3, 6, 9 ], [ 15, 19, 22 ]), C33([ 4, 5, 10 ], [ 16, 21, 23 ]), C33([ 7, 8, 11 ], [ 17, 18, 20 ]) K23(1,1) 0 15 0 -8 NO C44([0, 2, 3, 4], [12, 14, 15, 16]), C44([1, 8, 5, 11], [13, 23, 17, 20]), C44([6, 9, 10, 7], [18, 21, 22, 19]) K23(2,1) 15 33 5 -10 NO C44([0, 1, 2], [12, 13, 14]), C33([3, 9, 10 ], [ 15, 19, 22 ]), C33([4, 7, 11 ], [ 16, 21, 23 ]), C33([5, 6, 8 ], [17, 18, 20 ]). Table 2: Table representing Cylinder Additions to double covers Maps E1 E5 E6 χ Or. Handle Type T1(1,1) 4 18 - -8 NO C44([24, 2, 3, 4], [11, 14, 18, 17]),C44([12, 19, 21, 20], [1, 7, 22, 10]), C44([5, 8, 15, 23], [6, 9, 16, 13]) T1(1,2) 14 24 2 -8 NO C44([24, 2, 3, 4], [11, 14, 18, 17]), C44([12, 19, 21, 20], [1, 7, 22, 10]), C44([5, 8, 15, 23], [6, 9, 16, 13]), T2(1,1) 4 26 - -8 O C44([6, 7, 10, 21], [9, 18, 19, 22]), C44([24, 2, 3, 4], [12, 14, 15, 16]), C44([13, 20, 17, 23],[1, 8, 5, 11]) T2(2,1) 11 21 4 -10 NO C33([ 24, 2, 13 ], [ 11, 16, 19 ]), C33([ 1, 9, 14 ], [ 4, 7, 10 ]), C33([ 3, 22, 23 ], [ 15, 20, 21 ]), C33([ 5, 6, 8 ], [ 12, 17, 18 ]) T3(1,1) 0 24 - -8 O C44([24, 2, 3, 4], [12, 14, 15, 16]), C44([1, 8, 5, 11], [13, 20, 17, 23]), C44([18, 19, 22, 21], [6, 7, 10, 9]) T3(2,1) 9 17 6 -10 O C33([ 24, 1, 2 ], [ 12, 13, 14 ]), C33([ 3, 7, 10 ], [ 15, 19, 22 ]), C33([ 4, 21, 23 ], [ 9, 11, 16 ]), C33([ 5, 6, 8 ], [ 17, 18, 20 ]) T3(2,2) 20 23 10 -10 NO C33([ 24, 1, 2 ],[ 17, 18, 20 ]), C33([ 3, 7, 10 ], [ 12, 13, 14 ]), C33([ 4, 21, 23 ], [ 9, 11, 16 ]), C33([ 5, 6, 8 ], [ 15, 19, 22 ]) T3(2,3) 11 17 6 -10 NO C33([ 24, 1, 2 ], [ 17, 18, 20 ]), C33([ 3, 7, 10 ], [ 15, 19, 22 ]), C33([ 4, 21, 23 ], [ 9, 11, 16 ]), C33([ 5, 6, 8 ], [ 12, 13, 14 ]) T3(2,4) 21 18 12 -10 O C33([ 24, 1, 2 ], [ 15, 19, 22 ]), C33([ 3, 7, 10 ],[ 12, 13, 14 ]), C33([ 4, 21, 23 ], [ 9, 11, 16 ]), C33([ 5, 6, 8 ], [ 17, 18, 20 ] 6 Lemma : 14 The maps defined in Example 13 above are mutually non isomorphic. Proof : Consider the enumeration of edges in G , G and G of the SEMs in this example 1 5 6 presented in tabular form above. From this it is immediate that the SEMs of this example are all non-isomorphic. 2 3 Proofs In this section we present proof of the results given in introduction section. Proof of Theorem 3: The proof follows by examples 9 and 10. It is obvious that N is not iso- morphic to any of T , T and T . Now, EG(G (T )) = [1,7],[2,22],[2,24],[3,7],[11,20],[12,20] 1 2 3 5 1 { } and EG(G (T )) = . EG(G (T )) = [2,7],[4,6],[14,19],[16,18] and EG(G (T )) = . EG(G 6 1 5 2 6 2 6 ∅ { } ∅ (T ))= [ 1, 6 ], [ 2, 7 ], [ 8, 24 ], [ 12, 20 ], [ 13, 18 ], [ 14, 19 ] . Hence T = T , T = T and 3 { } 1 6∼ 2 1 6∼ 3 T = T . From here it is also evident that T , T and T are not vertex transitive. Also, since 2 6∼ 3 1 2 3 EG(G (N)) = [1,3],[5,13],[6,8],[9,15],[11,24],[12,23],[14,19],[21,22] it follows that N is also 4 { } not vertex transitive. 2 Proof of Theorem 5: The result follows from Lemma 12 and Lemma 14. 2 Proof of Theorem 6: The result follows from Lemma 12 and Lemma 14. 2 Proof of Theorem 1 Let K be a SEM of type (35,4) on the surface of Euler characteristic 1. − Let V = V(K) = 0,1,2,...,10,11 denote the set of vertices of K. The proof of the theorem { } is by exhaustive search for all K. In what follows, the notation lk(i) = C ([i ,i ,i ],i ,i ,i ,i ) 7 1 2 3 4 5 6 7 for link of i will mean that [i,i ,i ,i ] forms a quadrangular facet and [i,i ,i ], [i,i ,i ], [i,i ,i ], 1 2 3 3 4 4 5 5 6 [i,i ,i ], [i,i ,i ] form triangular facets. We may assume without loss of generality that lk(0) = 6 7 7 1 C ([2,3,4],5,6,7,1). Then lk(2) = ([3,4,0],1,c,b,a). It is easy to see that (a,b,c) A B C, 7 ∈ ∪ ∪ where A = (6, 7, 8), (8, 6, 9), (8, 7, 6), (8, 9, 6), (8, 9, 10) , B = (5, 6, 7), (5, 6, 8), (5, 7, 6), (5, 7, { } { 8),(6, 5, 7), (6, 5, 8), (5, 8, 6), (5, 8, 9), (6, 7, 5), (6, 8, 5), (6, 8, 9), (7, 8, 5), (7, 8, 6), and } C = (7, 5, 6), (7, 5, 8), (7, 6, 8), (7, 8, 9), (8, 5, 6), (8, 5, 9), (8, 6, 5), (8, 7, 5), (8, 7, 9), (8, 9, { 5) } Claim : 15 The values (a,b,c) C are isomorphic to some (a,b,c) A B. ∈ ∈ ∪ We have (0,2)(3,4)(5,8)(6,7,9): (8,9,6) = (8,7,9) (5,7,9,6,8): (8,9,5) = ∼ ∼ (5,6,7) (5,7,6,8): (8,7,5) = (5,6,7) (5,8,6,9,7): (7,8,9) = (5,6,7) (5,6,7,8): (8,5,6) = ∼ ∼ ∼ (5,6,7) (5,6,8,7): (7,5,8) = (5,6,7) (5,7,8): (8,6,5) = (5,6,7) (5,6,8)(7,9): (8,5,9) = ∼ ∼ ∼ (5,6,7) (0,2)(3,4)(7,5,6): (7,5,6) = (6,7,5) (0,2)(3,4)(7,5,8): (7,6,8) = (8,6,5). This proves ∼ ∼ the Claim 15. Thus we have S = (6,7,8), (8,6,9), (8,7,6), (8,9,6), (8,9,10) (5,6,8), (5,7,6), (5,7,8), { } ∪{ (6,5,7), (6,5,8), (5,8,6), (5,8,9), (6,7,5), (6,8,5), (6,8,9), (7,8,5), (7,8,6) . } Claim : 16 There are no semi-equivelar maps(SEM) on a surface of Euler characteristic -1 for the values (a,b,c) B. ∈ By considering lk(1) we see immediately that if (a,b,c) = (5,6,7) then C (2,0,7) lk(1). When 3 ⊆ (a,b,c) = (5,6,8) this implies 3 or 4 appears in the squares containing 5, i.e. they appear in two 7 square. Thisisnotpossible. When(a,b,c) = (5,7,6)thenlk(2) = C ([3,4,0],1,6,7,5) thisimplies 7 lk(5) = ([7,a,6],0,4,3,2) then C (3,5,0,4) lk(2). Which is a contradiction. When (a,b,c) = 4 ⊆ (5,7,8) as in previous case we observe that this case is not possible. When (a,b,c) = (6,5,7) then lk(2) = C ([3,4,0],1,7,5,6). Considering links of 6,7, and 5 successively we get a contradiction 7 as in case of (a,b,c) = (5,6,8). When (a,b,c) = (6,5,8) then lk(6) = C ([7,8,9],3,2,5,0). 7 Considering link of 5 we get a contradiction as in the case (a,b,c) = (5,6,8). When (a,b,c) = (5,8,6) then considering links of 2 and 5 successively we see that deg(4) 4. Similarly, when ≤ (a,b,c) = (5,8,9) as in previous case this case also leads to a contradiction. When (a,b,c) = (6,7,5) then considering links of 5 and 7 successively we get a contradiction as in case (a,b,c) = (5,6,8). When (a,b,c) = (6,8,5) then considering link 2 we get deg(5) 8. ≥ When(a,b,c) = (6,8,9)thenlk(2) = C ([3,4,0],1,9,8,6) thisimplieslk(6) = C ([8,10,7],0,5, 7 7 3,2) or lk(6) = C ([8,10,5],0,7,3,2). In the first case, successively considering links of 3, 5, 7, 4, 7 11, 9 and 1 we see that this case is not possible. In the second case, lk(7) = C ([9,11,1],0,6,3,x) 7 or lk(7) = C ([11,9,1],0,6,3,x), for some x V. In the first case, 19 is both a non-edge and an 7 ∈ edge in M and in second case, C (9,2,0,7,11) lk(1). A contradiction. When (a,b,c) = (7,8,5) 5 ⊆ then considering links of 2 and 5 we get a contradiction as in case (a,b,c) = (5,6,8). When (a,b,c) = (7,8,6) then link 6 has more than 7 vertices. When(a,b,c) = (7,8,9)thenlk(2) = C ([3,4,0],1,9,8,7) thisimplieslk(7) = C ([8,10,1],0,6, 7 7 3,2) or lk(7) = C ([8,10,6],0,1,3,2). When lk(7) = C ([8,10,1],0,6,3,2) we get lk(1) = 7 7 C ([10,8,7],0,2,9,d) where d 4,5,11 . When d = 4 then lk(4) = C ([3,2,0],5,9,1,10) or 7 7 ∈ { } lk(4) = C ([3,2,0],5,10,1,9). Firstcaseimplieslk(9) = C ([11,6,5],4,1,2,8) thenC (4,0,6,11,9) 7 7 5 lk(5). In second case considering lk(9) we see that 8 or 3 appear in two square. When ⊆ d = 5 then lk(1) = C ([10,8,7],0,2,9,5), this implies lk(5) = C ([9,11,6], 0,4,10,1), lk(6) = 7 7 C ([11,9,5],0,7,3,e) where e 4,8 . If e = 4 then lk(4) = C ([0,2,3],6,11,10,5) this implies 7 7 ∈ { } C (4,6,7,2,0) lk(3). If e = 8, lk(8) has more than seven vertices. When d = 11 we get lk(3) = 5 ⊆ C ([4,0,2],7,6,x,y) there (x,y) (8,9),(9,8), (8,10),(10,8),(10,11),(11,10),(9,11),(11,9) . 7 ∈ { } If (x,y) (8,9),(9,11),(11,9) then we do not get three quadrangles in the map. So, (x,y) ∈ { } ∈ (9,8),(8,10),(10,8),(10,11),(11,10) . { } If (x,y) = (9,8) then lk(3) = C ([4,0,2],7,6,9,8). So, lk(9) = C ([11,5,6],3,8,2,1). This 7 7 implies C (5,0,7,3,9,11) lk(6). Which is not possible. If (x,y) = (8,10) then lk(3) = 6 ⊆ C ([4,0,2],7,6,8,10), lk(8) = C ([7,1,10],3,6,9,2), lk(6) = C ([9,11,5],0,7,3,8). Thenlk(9)has 7 7 7 a 6-cycle. If (x,y) = (10,8) then lk(3) = C ([4,0,2],7,6,10,8) and lk(8) = C ([7,1,10],3,4,9,2). 7 7 This implies lk(6) = C ([5,9,11],10,3,7,0). This implies lk(10) has a6-cycle. Thisis notallowed. 7 If (x,y) = (10,11) then lk(3) = C ([4,0,2],7,6,10,11) and lk(10) = C ([8,7,1],11,3,6,f). Possi- 7 7 ble values of f = 5 or 9. If f = 5, then C (5,10,3,7,0) lk(6). If f = 9 then C (9,10,1,7,2) 5 5 ⊆ ⊆ lk(8). A contradiction. If (x,y) = (11,10) then lk(3) = C ([4,0,2],7,6,11,10). This implies 7 lk(10) = C ([8,7,1],11,3,4,g), for some g V. It is easy to see that g = 5 or 9. When g = 5, we 7 ∈ getC (5,10,3,2,0) lk(4). Wheng = 9thenwegetC (9,10,1,7,2) lk(8). Thisisnotpossible. 5 5 ⊆ ⊆ So, d = 11. Hence lk(7) = C ([8,10,6],0,1,3,2). Inthis case, weget lk(1) = C ([5,11,9],2,0,7,3) 7 7 6 or lk(1) = C ([11,5,9],2,0,7,3). 7 When lk(1) = C ([5,11,9],2,0,7,3) we get lk(5) = C ([1,9,11],4,0,6,3), lk(6) = C ([7,8,10], 7 7 7 4, 3, 5, 0), lk(4) = C ([3,2,0],5,11,10,6), lk(3) = C ([4,0,2],7,1,5,6). So, lk(11) = C ([9,1,5], 7 7 7 4, 10, w, z). Butthen 0,2,3,6,7 doesnot belongs to lk(11). Thatis deg(11) 6. When lk(1) = { } ≤ C ([11,5,9],2,0,7,3) we get lk(3) = C ([4,0,2],7,1,11,10). This implies lk(4) = C (10,[3,2,0], 7 7 7 5,p,q), for some p,q V. It is easy to see that (p,q) (8,9), (8,11), (9,8), (11,8) . If (p,q) = ∈ ∈ { } 8 (8,11), then lk(8) has more than seven vertices. If (p,q) = (9,8) then C 5,4,8,2,1,11) lk(9). ( ⊆ When (p,q) = (11,8) then lk(4) = C ([0,2,3],10,8,11,5). So, lk(8) = C ([10,6,7],2,9,11,4). 7 7 This implies 28 and 811 are edges in lk(9) which is not possible. When (p,q) = (8,9) then lk(4) = C ([0,2,3],10,9,8,5), lk(8) = C ([10,6,7],2,9,4,5), lk(9) = C ([1,11,5],10,4,8,2), lk(10) = 7 7 7 C ([8,7,6],3,4,9,5) and lk(5) = C ([11,1,9],10,8,4,0). This implies lk(6) = C ([7,8,10],3,11, 7 7 7 5,0). But then, C (3,11,10) lk(3) which is a contradiction. This proves the Claim 16. 3 ∈ Thuswemayassume(a,b,c) A. Inotherwords(a,b,c) (6,7,8), (8,6,9), (8,7,6), (8,9,6), ∈ ∈ { (8,9,10) . } Case 1: When (a,b,c) = (6,7,8), lk(2) = C ([3,4,0],1,8,7,6). So, lk(6) = C ([8,1,5],0,7,2,3), 7 7 lk(6) = C ([8,9,5],0,7,2,3), lk(6) = C ([1,8,5],0,7,2,3) or lk(6) = C ([9,8,5],0,7,2,3). When 7 7 7 lk(6) = C ([8,1,5],0,7,2,3), considering lk(7), we get 8 in two quadrangles. When lk(6) = 7 C ([8,9,5],0,7,2,3), considering links of 8 and 7 we get either 3 or 9 in two quadrangles. This is 7 notpossible. Similarly, whenlk(6) = C ([1,8,5],0,7,2,3) theneither 1or8willbein two squares. 7 Thus lk(6) = C ([9,8,5],0,7,2,3). This implies lk(7) = C ([11,10,1],0,6,2,8). This implies 7 7 lk(8) = C ([5,6,9],1,2,7,11) or lk(8) = C ([5,6,9],11,7,2,1). If lk(8) = ([5,6,9],1,2,7,11) 7 7 then considering links of 1 and 5 we get C (10,5,8,7,1) lk(11). This is not possible. So, 5 ⊆ lk(8) = C ([5,6,9],11,7,2,1) now completing successively we get lk(1) = C ([7,11,10],5, 8,2,0), 7 7 lk(5) = C ([6,9,8],1,10,4,0), lk(10) = C ([1,7,11],3,9,4,5), lk(9) = C ([6,5,8], 11,4,10, 3), 7 7 7 lk(3) = C ([2,0,4],11,10,9,6), lk(4) = C ([3,2,0],5,10,9,11), lk(11) = C ([10,1,7],8,9,4,3). 7 7 7 This is the object K of Example 7 with vertex 10 replaced by u and vertex 11 replaced by v. 1 Case 2: When (a,b,c) = (8,6,9) then lk(2) = C ([3,4,0],1,9,6,8). This implies lk(6) = 7 C (0,7,9,2,[8,d,5]), lk(6) = C (0,7,8,2,[9,d,5]), lk(6) = C (0,5,9,2,[8,d,7]) orlk(6) = C (0,5,8, 7 7 7 7 2,[9,d,7]), for some d V. If lk(6) = C (0,7,8,2,[9,d,5]), then it is easy to see that d = 1 7 ∈ or 10. If d = 1, then C (1,2,6,5) lk(9). If d = 10 then for some x,y,z V we have 4 ⊆ ∈ lk(7) = C (0,6,8,x,[y,z,1]) or lk(7) = C (6,0,1,x,[y,z,8]). But in both cases lk(7) can not 7 7 be completed. If lk(6) = C (0,7,9,2,[8,d,5]), then d = 1 or 10 If d = 1, we get lk(7) = 7 C ([11,10,9],6,0,1,e) or lk(7) = C ([10,11,9],6,0,1,e), for some e V. In the first case, 7 7 ∈ i.e. when lk(7) = C ([11,10,9],6,0,1,e) we see that e 3,4,5,8 . If e = 3 or 4 then lk(1) 7 ∈ { } has more than seven vertices. When e = 5 then we get lk(1) = C ([5,6,8],9,2,0,7), lk(8) = 7 C ([6,5,1],9,10,3,2), lk(9) = C ([7,11,10],8,1,2,6) and lk(5) = C ([6,8,1],7,11,4,0). But then 7 7 7 lk(11) can not be completed since 0,1,2,6,8 does not belong to lk(11). So, e = 8. Then lk(7) = { } C ([11,10,9],6,0,1,8). Thisimplies lk(9) = C ([7,11,10],5,1,2,6), lk(5) = C ([6,8,1],9,10,4,0). 7 7 7 Then considering lk(10) we see that C (3,10,5,0,2) lk(4). This is not possible. When lk(7) = 5 ⊆ C ([10,11,9],6,0,1,e), we see that e 3,4,5,8 . If e = 3 or 4 then lk(1) has more than seven 7 ∈ { } vertices. If e = 5, then lk(1) = C ([5,6,8],9,2,0,7). This implies lk(9) = C ([7,10,11],8,1,2,6) 7 7 lk(8) = C ([6,5,1],9,11,3,2) and lk(6) = C ([5,1,8],2,9,7,0). Then 0,1,2,4,5 lk(11). This 7 7 { } 6∈ is not possible. If e = 8 then lk(7) = C ([10,11,9],6,0,1,8), lk(6) = C ([8,1,5],0,7,9,2), 7 7 lk(8) = C ([1,5,6],2,3,10,7), lk(1) = C ([5,6,8],7,0,2,9), lk(5) = C ([6,8,1],9,11,4,0) and 7 7 7 lk(9) = C ([7,10,11],5,1,2,6). Then 0,1,2,6,8 lk(11). This is not possible. Thus, d = 1. 7 { } 6∈ 6 Hence d = 10. Then lk(6) = C ([5,10,8],2,9,7,0). This implies that for some x,y,z V 7 ∈ we have lk(7) = C (0,6,9,x,[y,z,1]) or lk(7) = C (6,0,1,x,[y,z,9]). But in both these cases 7 7 lk(7) can not be completed. When lk(6) = C (0,5,9,2,[8,d,7]), we see that d = 1 or 10. If 7 d = 1 then C (0,1,8,6) lk(7). If d = 10 then lk(6) = C (0,5,9,2,[8,10,7]) this implies 4 7 ⊆ lk(5) = C ([11,1,9],6,0,4,e) where e 7,8,10 . If e = 7 or 8 then lk(7) has more than seven 7 ∈ { } vertices. If e = 10 then lk(5) = C ([9,1,11],10,4,0,6) this implies C (6,2,1,11,5) lk(9). This 7 5 ⊆ 9 is not possible. Subcase 2.1: When lk(6) = C (0,5,8,2,[9,d,7]), we see again that d = 1 or 10. In case 7 d = 1 we get C (1,0,6,9) lk(7). If d = 10, then lk(6) = C (0,5,8,2,[9,10,7]) and we get 4 7 ⊆ lk(5) = C ([1,11,8],6,0,4,e) or lk(5) = C ([11,1,8],6,0,4,e) for some e V. When lk(5) = 7 7 ∈ C ([11,1,8],6,0,4,e), we see that e 7,9,10 . If e = 7, then C 1,0,6,9) lk(9). If e = 9, 7 ( ∈ { } ⊆ then lk(9) has more than seven vertices. So, e = 10. Then lk(8) = C ([1,11,5],6,2,3, y), where 7 y 7,9,10 . ∈ { } When y = 7, then lk(8) = C ([1,11,5],6,2,3,7). Completing successively, we get lk(5) = 7 C ([8,1,11],10,4,0,6), lk(1) =C ([8,5,11],9,2,0,7), lk(7) = C ([6,9,10],3,8,1,0), lk(3) = ([4,0, 7 7 7 2],8,7,10,11), lk(10) = C ([7,6,9],4,5,11,3), lk(4) = C ([3,2,0],5,10,9,11), lk(9) = C ([6,7,10], 7 7 7 4,11,1,2) and lk(11) = C ([5,8,1],9,4,3,10). This is K of Example 7 with vertex 10 replaced 7 3 by u and vertex 11 replaced by v. When y = 9, then lk(8) = C ([1,11,5],6,2,3,9). Now, completing successively, we get lk(9) = 7 C ([6,7,10],3,8,1,2), lk(10) = C ([9,6,7],4,5,11,3), lk(1) = C ([8,5,11],7,0,2,9), lk(3) = C ([2,0, 7 7 7 7 4],11,10,9,8), lk(11) = C ([1,8,5],10,3,4,7), lk(7) = C ([10,9,6],0,1,11,4) andlk(4) = C ([3,2,0], 7 7 7 5,10,7,11). This is K of Example 7 with vertex 10 replaced by u and vertex 11 replaced by v 2 for convenience. In following lines the vertex set is retained as 0,1,2,...,10,11 for the sake of computational { } convenience. When we give isomorphism to K , K or K , we mean isomorphism is given to the 1 2 3 K in Case 1, to K in Subcase 2.1.2 and to K in Subcase 2.1.1 above. 1 2 3 Subcase 2.2: If lk(5) = C ([1,11,8],6,0,4,e) it is easy to see that e 7,9,10 . If e= 10, then 7 ∈ { } lk(1) has more than seven vertices. Ife = 7,thencompletingsuccessivelywegetlk(1)=C ([5,8,11],9,2,0,7), lk(7)=C ([10,9,6], 7 7 0,1,5,4), lk(4)=C ([3,2,0],5,7,10,11), lk(9)=C ([6,7,10],3,11,1,2), lk(5)=C ([1,11,8],6,0,4, 7 7 7 7), lk(8) = C ([5,1,11],10,3,2,6), lk(3) = C ([2,0,4],11,9,10,8), lk(11) = C ([1,5,8],10,4,3,9) 7 7 7 and lk(10) = C ([7,6,9],3,8,11,4). It is isomorphic to K by the map (0,2)(3,4)(5,8)(7,9). 7 2 Ife = 9,thenlk(5)=C ([8,11,1],9,4,0,6). Completingsuccessivelywegetlk(1)=C ([5,8,11], 7 7 7,0,2,9), lk(7)=C ([10,9,6],0,1,11,3), lk(3)=C ([2,0,4],11,7,10,8), lk(8)=C ([5,1,11],10,3, 7 7 7 2,6),lk(10)=C ([9,6,7],3,8,11,4), lk(4)=C ([3,2,0],5,9,10,11), lk(11)=C ([8,5,1],7,3,4,10) 7 7 7 andlk(9)=C ([6,7,10],4,5,1,2). ItisisomorphictoK bythemap(0,6,8,3,10,11,4,9,1)(2,7,5). 7 3 Case 3: When (a,b,c) = (8,7,6), we have lk(2) = C ([3,4,0],1,6,7,8). This implies lk(6) = 7 C (1,2,7,0,[5,a,b]) or lk(6) = C (5,0,7,2,[1,a,b]), for some a,b V. 7 7 ∈ If lk(6) = C (5,0,7,2,[1,a,b]), it is easy to see that lk(6) = C ([8,9,1],2,7,0,5), lk(6) = 7 7 C ([9,8,1],2,7,0,5) or lk(6) = C ([9,10,1],2,7,0,5). When lk(6) = C ([8,9,1],2,7,0,5) or 7 7 7 lk(6) = C ([9,8,1],2,7,0,5) then considering lk(7), it is easy to see that vertex 8 or 1 is in two 7 quadrangles. Thiscannothappen. Iflk(6) = C ([9,10,1],2,7,0,5) thenlk(7) = C ([8,5,11],1,0,6, 7 7 2) or lk(7) = ([8,11,5],1,0,6,2). In the first case we get C (2,0,7,10,9,6) lk(1). In the second 6 ⊆ case we see that lk(5) has more than seven vertices. In the second case, we get lk(6) = C (1,2,7,0,[5,8,9]), lk(6) = C (1,2,7,0,[5,9,8]) or lk(6) = 7 7 C (1,2,7,0,[5,9,10]). If lk(6) = C (1,2,7,0,[5,9,8]) then lk(7) = C ([1,10,11],8,2,6,0). But 7 7 7 then lk(8) has more than seven vertices. This is not possible. If lk(6) = C (1,2,7,0,[5,9,10]), 7 then lk(1) = C ([7,8,11],10,6,2,0). In this case we get C (6,2,8,11,1,0) lk(7). This is not 7 6 ⊆ possible. When lk(6) = C (1,2,7,0,[5,8,9]) we get lk(7) = C (0,6,2,8,[11,10,1]) or lk(7) = 7 7 C (0,6,2,8,[10,11,1]). 7 If lk(7) = C (0,6,2,8,[11,10,1]) then lk(1) = C ([7,11,10],9,6,2, 0). This implies lk(8) = 7 7 10