Minimum genus embeddings of certain vertex- and/or edge-transitive graphs ========================================================================= Below is some information about minimum genus embeddings of certain vertex- and/or edge-transitive graphs, as described in the paper "New methods for finding minimum genus embeddings of graphs on orientable and non-orientable surfaces" in Ars Mathematica Contemporanea. For each graph X listed, this information includes a well-known name for X (and sometimes additional commentary about it), the order of X, the number of edges of X, the girth and diameter of X, and an indication of whether the graph is vertex-transitive, edge-transitive or symmetric (arc-transitive). Then in each of the orientable and non-orientable cases, we give the number of faces, the Euler characteristic (and the genus) of a minimum genus embedding of X, followed by a list of faces of a minimum genus embedding of X according to some labelling of the vertices of X. In all of the embeddings below, every face is bounded by a simple cycle in the graph. Each face of length k is given by a k-cycle, the entries of which are the vertices bounding the face, with consistent ordering in the orientable case. (Changing "(" and ")" to "[" and "]" will put the faces into a format that can be handled by Magma.) Marston Conder and Klara Stokes 18 December 2018 ========================================================================= The Folkman graph ================= This is the smallest finite graph that is semi-symmetric (which means it is bipartite, regular and edge-transitive, but not vertex-transitive). Number of vertices = 20 Number of edges = 40 Diameter = 4 Girth = 4 Automorphism group of order 3840 Vertex-transitive? False Edge-transitive? True Arc-transitive? False Minimum genus orientable embedding ================================== Minimum orientable genus = 3 Number of faces = 16 Face lengths: ten of length 4, four of length 6, and two of length 8 Euler characteristic = -4 Faces: ( 1, 11, 6, 14 ), ( 7, 12, 2, 13 ), ( 5, 12, 10, 20 ), ( 9, 11, 4, 16 ), ( 1, 18, 6, 19 ), ( 7, 18, 2, 17 ), ( 5, 15, 10, 19 ), ( 9, 15, 4, 17 ), ( 3, 14, 8, 16 ), ( 3, 20, 8, 13 ), ( 1, 14, 3, 13, 2, 18 ), ( 7, 13, 8, 14, 6, 18 ), ( 5, 20, 3, 16, 4, 15 ), ( 9, 16, 8, 20, 10, 15 ), ( 1, 19, 10, 12, 7, 17, 4, 11 ), ( 5, 19, 6, 11, 9, 17, 2, 12 ). The automorphism group of this embedding is elementary abelian of order 8, generated by the three automorphisms inducing the permutations x = (1, 2)(4, 5)(6, 7)(9, 10)(11, 12)(13, 14)(16, 20)(17, 19), y = (1, 4)(2, 5)(6, 9)(7, 10)(13, 20)(14, 16)(15, 18)(17, 19), and z = (1, 6)(2, 7)(3, 8)(4, 9)(5, 10). This embedding is reflexible. All three of x, y and z reverse orientation. Minimum genus non-orientable embedding ====================================== Minimum non-orientable genus = 6 Number of faces = 16 Face lengths: ten of length 4, five of length 6, and one of length 10 Euler characteristic = -4 Faces: ( 1, 11, 6, 14 ), ( 1, 19, 6, 18 ), ( 5, 19, 10, 12 ), ( 5, 20, 10, 15 ), ( 4, 11, 9, 16 ), ( 3, 20, 8, 16 ), ( 4, 17, 9, 15 ), ( 3, 13, 8, 14 ), ( 2, 17, 7, 12 ), ( 2, 13, 7, 18 ), ( 1, 11, 9, 15, 10, 19 ), ( 5, 19, 6, 14, 8, 20 ), ( 4, 11, 6, 18, 7, 17 ), ( 3, 13, 7, 12, 10, 20 ), ( 2, 13, 8, 16, 9, 17 ), ( 1, 14, 3, 16, 4, 15, 5, 12, 2, 18 ). The automorphism group of this embedding is dihedral of order 10, generated by the two automorphisms inducing the permutations r = (2, 3)(4, 5)(7, 8)(9, 10)(11, 19)(12, 16)(14, 18)(17, 20) and s = (1, 4, 2, 3, 5)(6, 9, 7, 8, 10)(11, 17, 13, 20, 19)(12, 14, 15, 18, 16). ========================================================================= Cartesian product C_3 ☐ C_3 ☐ C_3 ================================= Number of vertices = 27 Number of edges = 81 Diameter = 3 Girth = 3 Automorphism group of order 1296 Vertex-transitive? True Edge-transitive? True Arc-transitive? True Minimum genus orientable embedding ================================== Minimum orientable genus = 7 Number of faces = 42 Face lengths: 18 of length 3, plus 18 of length 4, and 6 of length 6 Euler characteristic = -12 Faces: ( 4, 6, 5 ), ( 7, 8, 9 ), ( 10, 16, 13 ), ( 17, 16, 18 ), ( 19, 22, 25 ), ( 11, 12, 10 ), ( 2, 20, 11 ), ( 23, 20, 26 ), ( 24, 22, 23 ), ( 21, 20, 19 ), ( 3, 12, 21 ), ( 5, 8, 2 ), ( 15, 6, 24 ), ( 18, 12, 15 ), ( 9, 6, 3 ), ( 13, 22, 4 ), ( 26, 8, 17 ), ( 25, 16, 7 ), ( 1, 2, 8, 7 ), ( 1, 3, 6, 4 ), ( 1, 4, 22, 19 ), ( 14, 15, 12, 11 ), ( 1, 7, 16, 10 ), ( 14, 13, 16, 17 ), ( 1, 10, 12, 3 ), ( 14, 17, 8, 5 ), ( 27, 26, 20, 21 ), ( 27, 25, 22, 24 ), ( 1, 19, 20, 2 ), ( 14, 11, 20, 23 ), ( 14, 23, 22, 13 ), ( 27, 24, 6, 9 ), ( 27, 21, 12, 18 ), ( 14, 5, 6, 15 ), ( 27, 18, 16, 25 ), ( 27, 9, 8, 26 ), ( 2, 3, 21, 24, 23, 5 ), ( 3, 2, 11, 17, 18, 9 ), ( 4, 7, 9, 18, 15, 13 ), ( 7, 4, 5, 23, 26, 25 ), ( 10, 19, 25, 26, 17, 11 ), ( 13, 15, 24, 21, 19, 10 ). The automorphism group of this embedding has order 36, generated by the two automorphisms inducing the permutations x = (2, 7)(3, 4)(5, 9)(10, 19)(11, 25)(12, 22)(13, 21)(14, 27) (15, 24)(16, 20)(17, 26)(18, 23) and y = (1, 14, 27)(2, 15, 25)(3, 13, 26)(4, 23, 21, 10, 17, 9) (5, 24, 19, 11, 18, 7)(6, 22, 20, 12, 16, 8). This embedding is reflexible. Both x and y reverse orientation. Minimum genus non-orientable embedding ====================================== Minimum non-orientable genus = 13 Number of faces = 43 Face lengths: 24 of length 3, plus 12 of length 4, and 7 of length 6 Euler characteristic = -11 Faces: ( 1, 2, 3 ), ( 1, 4, 7 ), ( 7, 9, 8 ), ( 3, 9, 6 ), ( 4, 6, 5 ), ( 2, 5, 8 ), ( 2, 11, 20 ), ( 3, 12, 21 ), ( 4, 13, 22 ), ( 7, 16, 25 ), ( 8, 26, 17 ), ( 6, 15, 24 ), ( 10, 12, 11 ), ( 19, 21, 20 ), ( 10, 13, 16 ), ( 16, 18, 17 ), ( 19, 25, 22 ), ( 25, 26, 27 ), ( 12, 18, 15 ), ( 22, 24, 23 ), ( 13, 14, 15 ), ( 21, 27, 24 ), ( 20, 23, 26 ), ( 11, 17, 14 ), ( 1, 10, 11, 2 ), ( 1, 3, 21, 19 ), ( 1, 10, 13, 4 ), ( 7, 16, 18, 9 ), ( 1, 7, 25, 19 ), ( 8, 9, 27, 26 ), ( 3, 12, 18, 9 ), ( 4, 5, 23, 22 ), ( 5, 6, 15, 14 ), ( 6, 24, 27, 9 ), ( 2, 20, 23, 5 ), ( 5, 8, 17, 14 ), ( 10, 12, 15, 24, 22, 19 ), ( 10, 16, 17, 26, 20, 19 ), ( 11, 17, 18, 27, 21, 20 ), ( 13, 22, 25, 27, 18, 15 ), ( 11, 12, 21, 24, 23, 14 ), ( 13, 16, 25, 26, 23, 14 ), ( 2, 3, 6, 4, 7, 8 ). The automorphism group of this embedding is dihedral of order 12, generated by the two automorphisms inducing the permutations r = (2, 3)(4, 7)(5, 9)(6, 8)(10, 19)(11, 21)(12, 20)(13, 25)(14, 27) (15, 26)(16, 22)(17, 24)(18, 23) and s = (1, 5, 9)(2, 8, 7, 4, 6, 3)(10, 14, 18)(11, 17, 16, 13, 15, 12) (19, 23, 27)(20, 26, 25, 22, 24, 21). ========================================================================= The Doyle-Holt graph ==================== This is the smallest finite graph that is half-arc-transitive (meaning that it is vertex- and edge-transitive but not arc-transitive). Number of vertices = 27 Number of edges = 54 Diameter = 3 Girth = 5 Automorphism group of order 54 Vertex-transitive? True Edge-transitive? True Arc-transitive? False Minimum genus orientable embedding ================================== Minimum orientable genus = 5 Number of faces = 19 Face lengths: 14 of length 5, one of length 6, and four of length 8 Euler characteristic = -8 Faces: ( 1, 13, 20, 5, 25 ), ( 1, 24, 11, 6, 18 ), ( 1, 18, 19, 8, 13 ), ( 1, 25, 12, 9, 24 ), ( 2, 16, 20, 9, 14 ), ( 3, 27, 11, 8, 23 ), ( 2, 14, 21, 7, 22 ), ( 3, 23, 10, 7, 15 ), ( 2, 22, 18, 6, 26 ), ( 3, 15, 25, 5, 17 ), ( 2, 26, 10, 23, 16 ), ( 3, 17, 21, 14, 27 ), ( 4, 16, 23, 8, 19 ), ( 4, 27, 14, 9, 12 ), ( 12, 25, 15, 19, 18, 22 ), ( 4, 12, 22, 7, 10, 5, 20, 16 ), ( 4, 19, 15, 7, 21, 6, 11, 27 ), ( 5, 10, 26, 13, 8, 11, 24, 17 ), ( 6, 21, 17, 24, 9, 20, 13, 26 ). The automorphism group of this embedding is cyclic of order 2, generated by the automorphism inducing the permutation x = (2, 3)(5, 6)(8, 9)(10, 21)(11, 20)(12, 19)(13, 24)(14, 23)(15, 22) (16, 27)(17, 26)(18, 25). This embedding is chiral, with x preserving orientation. Minimum genus non-orientable embedding ====================================== Minimum non-orientable genus = 8 Number of faces = 21 Face lengths: 18 of length 5, and three of length 6 Euler characteristic = -6 Faces: ( 1, 13, 8, 19, 18 ), ( 1, 24, 9, 12, 25 ), ( 2, 14, 9, 20, 16 ), ( 4, 16, 2, 22, 12 ), ( 2, 22, 7, 10, 26 ), ( 4, 27, 3, 15, 19 ), ( 3, 23, 8, 11, 27 ), ( 3, 15, 7, 21, 17 ), ( 5, 17, 3, 23, 10 ), ( 7, 10, 5, 25, 15 ), ( 5, 25, 1, 13, 20 ), ( 7, 21, 6, 18, 22 ), ( 6, 26, 2, 14, 21 ), ( 6, 18, 1, 24, 11 ), ( 8, 11, 6, 26, 13 ), ( 8, 19, 4, 16, 23 ), ( 9, 20, 5, 17, 24 ), ( 9, 12, 4, 27, 14 ), ( 10, 23, 16, 20, 13, 26 ), ( 11, 24, 17, 21, 14, 27 ), ( 12, 22, 18, 19, 15, 25 ). The automorphism group of this embedding has order 18, and is generated by the three automorphisms inducing the permutations r = (2, 3)(5, 6)(8, 9)(10, 21)(11, 20)(12, 19)(13, 24)(14, 23)(15, 22) (16, 27)(17, 26)(18, 25), s = (1, 2, 3)(4, 5, 6)(7, 8, 9)(10, 11, 12)(13, 14, 15)(16, 17, 18) (19, 20, 21)(22, 23, 24)(25, 26, 27) and t = (1, 4, 7)(2, 5, 8)(3, 6, 9)(10, 13, 16)(11, 14, 17)(12, 15, 18) (19, 22, 25)(20, 23, 26)(21, 24, 27). ========================================================================= The dual Menger graph of the Gray configuration =============================================== Number of vertices = 27 Number of edges = 81 Diameter = 3 Girth = 3 Automorphism group of order 1296 Vertex-transitive? True Edge-transitive? True Arc-transitive? True Minimum genus orientable embedding ================================== Minimum orientable genus = 6 Number of faces = 44 Face lengths: 26 of length 3, plus 12 of length 4, and 6 of length 6 Euler characteristic = -10 Faces: ( 1, 4, 8 ), ( 15, 9, 19 ), ( 2, 3, 11 ), ( 2, 6, 5 ), ( 1, 7, 10 ), ( 15, 18, 14 ), ( 3, 8, 17 ), ( 4, 19, 12 ), ( 9, 11, 24 ), ( 14, 16, 6 ), ( 5, 13, 7 ), ( 10, 26, 18 ), ( 3, 27, 7 ), ( 4, 22, 18 ), ( 9, 23, 6 ), ( 14, 11, 25 ), ( 5, 8, 20 ), ( 10, 19, 21 ), ( 12, 23, 20 ), ( 24, 27, 21 ), ( 17, 22, 25 ), ( 13, 23, 21 ), ( 26, 27, 25 ), ( 16, 22, 20 ), ( 12, 24, 17 ), ( 13, 16, 26 ), ( 1, 8, 3, 2 ), ( 15, 19, 4, 1 ), ( 2, 11, 9, 15 ), ( 2, 15, 14, 6 ), ( 1, 2, 5, 7 ), ( 15, 1, 10, 18 ), ( 3, 17, 25, 27 ), ( 4, 12, 20, 22 ), ( 9, 24, 21, 23 ), ( 14, 25, 22, 16 ), ( 5, 20, 23, 13 ), ( 10, 21, 27, 26 ), ( 4, 18, 26, 16, 20, 8 ), ( 9, 6, 16, 13, 21, 19 ), ( 3, 7, 13, 26, 25, 11 ), ( 5, 6, 23, 12, 17, 8 ), ( 10, 7, 27, 24, 12, 19 ), ( 14, 18, 22, 17, 24, 11 ). The automorphism group of this embedding is cyclic of order 6, and is generated by the automorphism inducing the permutation x = (1, 2, 15)(3, 14, 4, 5, 9, 10)(6, 19, 7, 11, 18, 8) (12, 13, 24, 26, 17, 16)(20, 23, 21, 27, 25, 22). This embedding is reflexible, with x reversing orientation. Minimum genus non-orientable embedding ====================================== Minimum non-orientable genus = 11 Number of faces = 45 Face lengths: 18 of length 3, and 27 of length 4 Euler characteristic = -9 Faces: ( 1, 4, 8 ), ( 1, 10, 7 ), ( 4, 12, 19 ), ( 14, 18, 15 ), ( 25, 26, 27 ), ( 9, 19, 15 ), ( 17, 22, 25 ), ( 10, 18, 26 ), ( 5, 7, 13 ), ( 9, 24, 11 ), ( 3, 8, 17 ), ( 2, 11, 3 ), ( 2, 6, 5 ), ( 12, 23, 20 ), ( 16, 20, 22 ), ( 13, 21, 23 ), ( 6, 14, 16 ), ( 21, 24, 27 ), ( 1, 2, 3, 7 ), ( 1, 15, 18, 4 ), ( 1, 15, 19, 10 ), ( 2, 15, 9, 6 ), ( 11, 25, 17, 24 ), ( 1, 2, 5, 8 ), ( 4, 18, 10, 19 ), ( 2, 11, 14, 15 ), ( 3, 11, 25, 27 ), ( 12, 19, 21, 24 ), ( 14, 25, 26, 16 ), ( 10, 21, 13, 26 ), ( 6, 23, 13, 16 ), ( 8, 17, 12, 20 ), ( 5, 6, 23, 20 ), ( 9, 19, 21, 23 ), ( 14, 25, 22, 18 ), ( 3, 7, 5, 8 ), ( 6, 14, 11, 9 ), ( 3, 27, 24, 17 ), ( 7, 27, 21, 10 ), ( 4, 8, 20, 22 ), ( 16, 26, 18, 22 ), ( 5, 13, 16, 20 ), ( 9, 23, 12, 24 ), ( 4, 12, 17, 22 ), ( 7, 27, 26, 13 ). The automorphism group of this embedding has order 108, and is generated by the two automorphisms inducing the permutations r = (1, 25)(2, 11)(4, 22)(5, 24)(6, 9)(7, 27)(8, 17)(10, 26)(12, 20) (13, 21)(14, 15)(16, 19) and s = (1, 2, 15)(3, 14, 4, 5, 9, 10)(6, 19, 7, 11, 18, 8) (12, 13, 24, 26, 17, 16)(20, 23, 21, 27, 25, 22). ========================================================================= Tutte's 8-cage ============== This is the smallest 5-arc-transitive 3-valent graph. Number of vertices = 30 Number of edges = 45 Diameter = 4 Girth = 8 Automorphism group of order 1440 Vertex-transitive? True Edge-transitive? True Arc-transitive? True Minimum genus orientable embedding ================================== Minimum orientable genus = 4 Number of faces = 9 Face lengths: three of length 8, three of length 10, and three of length 12 Euler characteristic = -6 Faces: ( 1, 2, 5, 11, 23, 16, 8, 4 ), ( 1, 3, 9, 21, 28, 12, 6, 2 ), ( 1, 4, 10, 18, 26, 19, 7, 3 ), ( 5, 13, 25, 17, 30, 14, 26, 18, 27, 11 ), ( 9, 17, 25, 22, 24, 15, 23, 11, 27, 21 ), ( 10, 22, 25, 13, 29, 20, 28, 21, 27, 18 ), ( 2, 6, 14, 30, 16, 23, 15, 7, 19, 29, 13, 5 ), ( 3, 7, 15, 24, 12, 28, 20, 8, 16, 30, 17, 9 ), ( 4, 8, 20, 29, 19, 26, 14, 6, 12, 24, 22, 10 ). The automorphism group of this embedding is cyclic of order 3, and is generated by the automorphism inducing the permutation x = (2, 3, 4)(5, 9, 10)(6, 7, 8)(11, 21, 18)(12, 19, 16)(13, 17, 22) (14, 15, 20)(23, 28, 26)(24, 29, 30). This embedding is chiral, with x preserving orientation. Minimum genus non-orientable embedding ====================================== Minimum non-orientable genus = 6 Number of faces = 11 Face lengths: ten of length 8, and one of length 10 Euler characteristic = -4 Faces: ( 1, 2, 5, 11, 23, 16, 8, 4 ), ( 11, 5, 13, 25, 22, 10, 18, 27 ), ( 25, 13, 29, 20, 28, 21, 9, 17 ), ( 20, 29, 19, 26, 14, 30, 16, 8 ), ( 26, 19, 7, 3, 1, 4, 10, 18 ), ( 3, 7, 15, 23, 11, 27, 21, 9 ), ( 23, 15, 24, 22, 25, 17, 30, 16 ), ( 22, 24, 12, 28, 20, 8, 4, 10 ), ( 28, 12, 6, 14, 26, 18, 27, 21 ), ( 14, 6, 2, 1, 3, 9, 17, 30 ), ( 2, 6, 12, 24, 15, 7, 19, 29, 13, 5 ). The automorphism group of this embedding is cyclic order 10, and is generated by the automorphism inducing the permutation r = (1, 11, 25, 20, 26, 3, 23, 22, 28, 14)(2, 5, 13, 29, 19, 7, 15, 24, 12, 6)(4, 27, 17, 8, 18, 9, 16, 10, 21, 30). ========================================================================= Hoffman-Singleton graph ======================= This is the unique regular graph with valency 7 and diameter 2 Number of vertices = 50 Number of edges = 175 Diameter = 2 Girth = 5 Automorphism group of order 252000 Vertex-transitive? True Edge-transitive? True Arc-transitive? True Minimum genus orientable embedding ================================== Minimum orientable genus = 29 Number of faces = 69 Face lengths: 64 of length 5, and five of length 6 Euler characteristic = -56 Faces: ( 1, 2, 34, 10, 27 ), ( 2, 3, 35, 6, 28 ), ( 3, 4, 31, 7, 29 ), ( 4, 5, 32, 8, 30 ), ( 5, 1, 33, 9, 26 ), ( 1, 5, 38, 7, 45 ), ( 2, 1, 39, 8, 41 ), ( 3, 2, 40, 9, 42 ), ( 4, 3, 36, 10, 43 ), ( 5, 4, 37, 6, 44 ), ( 1, 45, 13, 37, 39 ), ( 2, 41, 14, 38, 40 ), ( 3, 42, 15, 39, 36 ), ( 4, 43, 11, 40, 37 ), ( 5, 44, 12, 36, 38 ), ( 1, 46, 11, 12, 33 ), ( 2, 47, 12, 13, 34 ), ( 3, 48, 13, 14, 35 ), ( 4, 49, 14, 15, 31 ), ( 5, 50, 15, 11, 32 ), ( 6, 35, 17, 47, 7 ), ( 7, 31, 18, 48, 8 ), ( 8, 32, 19, 49, 9 ), ( 9, 33, 20, 50, 10 ), ( 10, 34, 16, 46, 6 ), ( 6, 37, 22, 23, 28 ), ( 7, 38, 23, 24, 29 ), ( 8, 39, 24, 25, 30 ), ( 9, 40, 25, 21, 26 ), ( 10, 36, 21, 22, 27 ), ( 6, 46, 21, 41, 44 ), ( 7, 47, 22, 42, 45 ), ( 8, 48, 23, 43, 41 ), ( 9, 49, 24, 44, 42 ), ( 10, 50, 25, 45, 43 ), ( 11, 29, 24, 34, 32 ), ( 12, 30, 25, 35, 33 ), ( 13, 26, 21, 31, 34 ), ( 14, 27, 22, 32, 35 ), ( 15, 28, 23, 33, 31 ), ( 11, 43, 17, 26, 29 ), ( 12, 44, 18, 27, 30 ), ( 13, 45, 19, 28, 26 ), ( 14, 41, 20, 29, 27 ), ( 15, 42, 16, 30, 28 ), ( 11, 46, 48, 18, 40 ), ( 12, 47, 49, 19, 36 ), ( 13, 48, 50, 20, 37 ), ( 14, 49, 46, 16, 38 ), ( 15, 50, 47, 17, 39 ), ( 16, 17, 43, 23, 38 ), ( 17, 18, 44, 24, 39 ), ( 18, 19, 45, 25, 40 ), ( 19, 20, 41, 21, 36 ), ( 20, 16, 42, 22, 37 ), ( 6, 7, 8, 9, 10 ), ( 11, 15, 14, 13, 12 ), ( 16, 20, 19, 18, 17 ), ( 21, 25, 24, 23, 22 ), ( 26, 28, 30, 27, 29 ), ( 31, 33, 35, 32, 34 ), ( 36, 39, 37, 40, 38 ), ( 41, 43, 45, 42, 44 ), ( 46, 49, 47, 50, 48 ), ( 1, 27, 18, 31, 21, 46 ), ( 2, 28, 19, 32, 22, 47 ), ( 3, 29, 20, 33, 23, 48 ), ( 4, 30, 16, 34, 24, 49 ), ( 5, 26, 17, 35, 25, 50 ). The automorphism group of this embedding is cyclic of order 5, and is generated by the automorphism inducing the permutation x = (1, 2, 3, 4, 5)(6, 7, 8, 9, 10)(11, 12, 13, 14, 15) (16, 17, 18, 19, 20)(21, 22, 23, 24, 25)(26, 27, 28, 29, 30) (31, 32, 33, 34, 35)(36, 37, 38, 39, 40)(41, 42, 43, 44, 45) (46, 47, 48, 49, 50). This embedding is chiral, with x preserving orientation. Minimum genus non-orientable embedding ====================================== Minimum non-orientable genus = 57 Number of faces = 70 Face lengths: 70 faces of length 5 Euler characteristic = -55 Faces: ( 1, 2, 34, 32, 5 ), ( 1, 5, 44, 18, 27 ), ( 1, 27, 22, 23, 33 ), ( 1, 33, 31, 15, 39 ), ( 1, 39, 24, 25, 45 ), ( 1, 45, 42, 16, 46 ), ( 1, 46, 21, 41, 2 ), ( 2, 3, 29, 26, 28 ), ( 5, 26, 9, 10, 50 ), ( 27, 10, 36, 12, 30 ), ( 33, 12, 13, 37, 20 ), ( 39, 37, 6, 7, 8 ), ( 45, 7, 47, 49, 19 ), ( 46, 49, 4, 3, 48 ), ( 2, 3, 35, 17, 47 ), ( 5, 26, 17, 43, 4 ), ( 27, 10, 43, 11, 29 ), ( 33, 12, 11, 40, 9 ), ( 39, 37, 40, 38, 36 ), ( 45, 7, 38, 14, 13 ), ( 46, 49, 14, 35, 6 ), ( 2, 28, 23, 38, 40 ), ( 5, 50, 15, 14, 38 ), ( 27, 30, 25, 35, 14 ), ( 33, 20, 16, 17, 35 ), ( 39, 8, 41, 43, 17 ), ( 45, 19, 32, 11, 43 ), ( 46, 48, 18, 40, 11 ), ( 2, 34, 13, 12, 47 ), ( 5, 44, 6, 37, 4 ), ( 27, 22, 47, 7, 29 ), ( 33, 31, 4, 49, 9 ), ( 39, 24, 29, 3, 36 ), ( 45, 42, 9, 26, 13 ), ( 46, 21, 36, 10, 6 ), ( 2, 40, 18, 44, 41 ), ( 5, 38, 23, 22, 32 ), ( 27, 14, 15, 31, 18 ), ( 33, 35, 25, 24, 23 ), ( 39, 17, 16, 42, 15 ), ( 45, 43, 41, 21, 25 ), ( 46, 11, 32, 34, 16 ), ( 3, 35, 32, 8, 48 ), ( 26, 17, 18, 19, 28 ), ( 10, 43, 23, 48, 50 ), ( 12, 11, 15, 28, 30 ), ( 37, 40, 25, 50, 20 ), ( 7, 38, 16, 30, 8 ), ( 49, 14, 41, 20, 19 ), ( 3, 36, 12, 44, 42 ), ( 26, 13, 37, 22, 21 ), ( 10, 6, 7, 31, 34 ), ( 12, 47, 49, 24, 44 ), ( 37, 4, 3, 42, 22 ), ( 7, 29, 26, 21, 31 ), ( 49, 9, 10, 34, 24 ), ( 4, 30, 16, 34, 31 ), ( 29, 20, 41, 44, 24 ), ( 9, 8, 32, 22, 42 ), ( 36, 19, 18, 31, 21 ), ( 13, 48, 23, 24, 34 ), ( 6, 28, 15, 42, 44 ), ( 47, 50, 25, 21, 22 ), ( 4, 30, 28, 23, 43 ), ( 29, 20, 50, 15, 11 ), ( 9, 8, 30, 25, 40 ), ( 36, 19, 20, 16, 38 ), ( 13, 48, 8, 41, 14 ), ( 6, 28, 19, 32, 35 ), ( 47, 50, 48, 18, 17 ). The automorphism group of this embedding is cyclic of order 7, and is generated by the automorphism inducing the permutation r = (2, 5, 27, 33, 39, 45, 46)(3, 26, 10, 12, 37, 7, 49) (4, 29, 9, 36, 13, 6, 47)(8, 19, 48, 28, 50, 30, 20) (11, 40, 38, 14, 35, 17, 43)(15, 25, 16, 41, 32, 18, 23) (21, 34, 44, 22, 31, 24, 42). ========================================================================= The Gray graph ============== This is the smallest 3-valent graph that is semi-symmetric, which means regular and edge-transitive but not vertex-transitive. Number of vertices = 54 Number of edges = 81 Diameter = 6 Girth = 8 Automorphism group of order 1296 Vertex-transitive? False Edge-transitive? True Arc-transitive? False Minimum genus orientable embedding ================================== Minimum orientable genus = 7 Number of faces = 15 Face lengths: six of length 8, six of length 12, and three of length 14 Euler characteristic = -12 Faces: ( 3, 29, 8, 42, 23, 46, 10, 33 ), ( 9, 32, 14, 36, 16, 52, 27, 47 ), ( 11, 34, 12, 45, 26, 54, 20, 39 ), ( 33, 10, 48, 24, 43, 6, 31, 15 ), ( 47, 27, 51, 25, 44, 17, 35, 13 ), ( 39, 20, 50, 18, 37, 5, 30, 7 ), ( 1, 29, 3, 36, 14, 41, 5, 37, 15, 31, 2, 28 ), ( 2, 32, 9, 45, 12, 38, 6, 43, 13, 35, 4, 28 ), ( 4, 34, 11, 42, 8, 40, 17, 44, 7, 30, 1, 28 ), ( 1, 30, 5, 41, 22, 51, 27, 52, 21, 40, 8, 29 ), ( 2, 31, 6, 38, 19, 50, 20, 54, 22, 41, 14, 32 ), ( 4, 35, 17, 40, 21, 48, 10, 46, 19, 38, 12, 34 ), ( 3, 33, 15, 37, 18, 53, 25, 51, 22, 54, 26, 49, 16, 36 ), ( 9, 47, 13, 43, 24, 53, 18, 50, 19, 46, 23, 49, 26, 45 ), ( 11, 39, 7, 44, 25, 53, 24, 48, 21, 52, 16, 49, 23, 42 ). The automorphism group of this embedding is dihedral of order 6, and is generated by the two automorphisms inducing the permutations x = (1, 2)(3, 15)(5, 14)(6, 8)(7, 9)(11, 13)(12, 17)(16, 18)(19, 21) (20, 27)(23, 24)(25, 26)(29, 31)(30, 32)(34, 35)(36, 37)(38, 40) (39, 47)(42, 43)(44, 45)(46, 48)(49, 53)(50, 52)(51, 54) and y = (1, 2, 4)(3, 9, 11)(5, 6, 17)(7, 15, 13)(8, 14, 12)(10, 27, 20) (16, 26, 23)(18, 24, 25)(19, 21, 22)(29, 32, 34)(30, 31, 35)(33, 47, 39)(36, 45, 42)(37, 43, 44)(38, 40, 41)(46, 52, 54)(48, 51, 50). This embedding is reflexible, with x reversing orientation. Minimum genus non-orientable embedding ====================================== Minimum non-orientable genus = 13 Number of faces = 16 Face lengths: Nine of length 8, four of length 12, and three of length 14 Euler characteristic = -11 Faces: ( 1, 28, 2, 31, 15, 33, 3, 29 ), ( 2, 28, 4, 35, 13, 47, 9, 32 ), ( 4, 28, 1, 30, 7, 39, 11, 34 ), ( 3, 33, 10, 46, 23, 49, 16, 36 ), ( 15, 33, 10, 48, 24, 53, 18, 37 ), ( 9, 47, 27, 52, 16, 49, 26, 45 ), ( 13, 47, 27, 51, 25, 53, 24, 43 ), ( 7, 39, 20, 50, 18, 53, 25, 44 ), ( 11, 39, 20, 54, 26, 49, 23, 42 ), ( 5, 37, 18, 50, 19, 38, 12, 45, 26, 54, 22, 41 ), ( 6, 43, 24, 48, 21, 40, 8, 42, 23, 46, 19, 38 ), ( 17, 44, 25, 51, 22, 41, 14, 36, 16, 52, 21, 40 ), ( 10, 48, 21, 52, 27, 51, 22, 54, 20, 50, 19, 46 ), ( 1, 29, 8, 42, 11, 34, 12, 38, 6, 31, 15, 37, 5, 30 ), ( 2, 32, 14, 36, 3, 29, 8, 40, 17, 35, 13, 43, 6, 31 ), ( 4, 34, 12, 45, 9, 32, 14, 41, 5, 30, 7, 44, 17, 35 ). The automorphism group of this embedding is dihedral of order 6, and is generated by the two automorphisms inducing the permutations r = (1, 2)(3, 15)(5, 14)(6, 8)(7, 9)(11, 13)(12, 17)(16, 18)(19, 21) (20, 27)(23, 24)(25, 26)(29, 31)(30, 32)(34, 35)(36, 37)(38, 40) (39, 47)(42, 43)(44, 45)(46, 48)(49, 53)(50, 52)(51, 54) and s = (1, 2, 4)(3, 9, 11)(5, 6, 17)(7, 15, 13)(8, 14, 12)(10, 27, 20) (16, 26, 23)(18, 24, 25)(19, 21, 22)(29, 32, 34)(30, 31, 35)(33, 47, 39)(36, 45, 42)(37, 43, 44)(38, 40, 41)(46, 52, 54)(48, 51, 50). ========================================================================= The smallest Iofinova-Ivanov graph II_1 ======================================= This is the second smallest semi-symmetric 3-valent graph. Number of vertices = 110 Number of edges = 165 Diameter = 7 Girth = 10 Automorphism group of order 1320 Vertex-transitive? False Edge-transitive? True Arc-transitive? False Minimum genus orientable embedding ================================== Minimum orientable genus = 15 Number of faces = 27 Face lengths: six of length 10, twelve of length 12, and nine of length 14 Euler characteristic = -28 Faces: ( 1, 56, 2, 60, 9, 73, 26, 72, 7, 58 ), ( 33, 91, 52, 101, 47, 105, 42, 99, 31, 80 ), ( 46, 84, 18, 94, 22, 69, 8, 68, 27, 103 ), ( 11, 75, 50, 96, 23, 64, 16, 88, 29, 83 ), ( 38, 85, 49, 98, 48, 82, 12, 76, 25, 87 ), ( 51, 106, 55, 89, 35, 92, 44, 108, 39, 107 ), ( 1, 57, 8, 69, 21, 95, 40, 76, 12, 62, 4, 56 ), ( 33, 74, 26, 73, 45, 97, 54, 108, 44, 86, 17, 91 ), ( 46, 93, 42, 105, 30, 67, 20, 88, 16, 77, 13, 84 ), ( 1, 58, 5, 70, 34, 106, 51, 77, 16, 64, 3, 57 ), ( 33, 80, 15, 79, 28, 75, 11, 62, 12, 82, 10, 74 ), ( 46, 103, 41, 78, 14, 85, 38, 86, 44, 92, 24, 93 ), ( 2, 56, 4, 63, 17, 86, 38, 87, 19, 66, 6, 59 ), ( 52, 91, 17, 63, 13, 77, 51, 107, 36, 102, 53, 110 ), ( 18, 84, 13, 63, 4, 62, 11, 83, 43, 104, 32, 65 ), ( 5, 65, 32, 100, 54, 97, 27, 68, 19, 87, 25, 70 ), ( 15, 59, 6, 71, 20, 67, 7, 72, 36, 107, 39, 79 ), ( 41, 110, 53, 90, 40, 95, 31, 99, 43, 83, 29, 78 ), ( 2, 59, 15, 80, 31, 95, 21, 89, 55, 109, 49, 85, 14, 60 ), ( 52, 110, 41, 103, 27, 97, 45, 96, 50, 109, 55, 106, 34, 101 ), ( 18, 65, 5, 58, 7, 67, 30, 98, 49, 109, 50, 75, 28, 94 ), ( 3, 64, 23, 90, 53, 102, 37, 104, 43, 99, 42, 93, 24, 61 ), ( 10, 82, 48, 100, 32, 104, 37, 66, 19, 68, 8, 57, 3, 61 ), ( 24, 92, 35, 71, 6, 66, 37, 102, 36, 72, 26, 74, 10, 61 ), ( 9, 60, 14, 78, 29, 88, 20, 71, 35, 89, 21, 69, 22, 81 ), ( 47, 101, 34, 70, 25, 76, 40, 90, 23, 96, 45, 73, 9, 81 ), ( 22, 94, 28, 79, 39, 108, 54, 100, 48, 98, 30, 105, 47, 81 ). The automorphism group of this embedding is cyclic of order 3, generated by the automorphism inducing the permutation x = (1, 33, 46)(2, 52, 18)(3, 10, 24)(4, 17, 13)(5, 15, 41)(6, 53, 32) (7, 31, 27)(8, 26, 42)(9, 47, 22)(11, 38, 51)(12, 44, 16) (14, 34, 28)(19, 36, 43)(20, 40, 54)(21, 45, 30)(23, 48, 35) (25, 39, 29)(49, 55, 50)(56, 91, 84)(57, 74, 93)(58, 80, 103) (59, 110, 65)(60, 101, 94)(62, 86, 77)(64, 82, 92)(66, 102, 104) (67, 95, 97)(68, 72, 99)(69, 73, 105)(70, 79, 78)(71, 90, 100) (75, 85, 106)(76, 108, 88)(83, 87, 107)(89, 96, 98). This embedding is chiral, with x preserving orientation. Minimum genus non-orientable embedding ====================================== Minimum non-orientable genus = 27 Number of faces = 30 Face lengths: 15 of length 10, and 15 of length 12 Euler characteristic = -25 Faces: ( 1, 56, 2, 59, 6, 66, 19, 68, 8, 57 ), ( 33, 91, 52, 110, 53, 102, 36, 72, 26, 74 ), ( 46, 84, 18, 65, 32, 104, 43, 99, 42, 93 ), ( 2, 56, 4, 62, 11, 83, 29, 78, 14, 60 ), ( 52, 91, 17, 86, 38, 87, 25, 70, 34, 101 ), ( 18, 84, 13, 77, 51, 107, 39, 79, 28, 94 ), ( 3, 64, 23, 96, 45, 73, 26, 74, 10, 61 ), ( 10, 82, 48, 98, 30, 105, 42, 93, 24, 61 ), ( 24, 92, 35, 89, 21, 69, 8, 57, 3, 61 ), ( 5, 70, 25, 76, 12, 82, 48, 100, 32, 65 ), ( 15, 79, 39, 108, 44, 92, 35, 71, 6, 59 ), ( 41, 78, 29, 88, 16, 64, 23, 90, 53, 110 ), ( 6, 71, 20, 88, 29, 83, 43, 104, 37, 66 ), ( 53, 90, 40, 76, 25, 87, 19, 66, 37, 102 ), ( 32, 100, 54, 108, 39, 107, 36, 102, 37, 104 ), ( 1, 56, 4, 63, 13, 77, 16, 88, 20, 67, 7, 58 ), ( 33, 91, 17, 63, 4, 62, 12, 76, 40, 95, 31, 80 ), ( 46, 84, 13, 63, 17, 86, 44, 108, 54, 97, 27, 103 ), ( 1, 57, 3, 64, 16, 77, 51, 106, 34, 70, 5, 58 ), ( 33, 74, 10, 82, 12, 62, 11, 75, 28, 79, 15, 80 ), ( 46, 93, 24, 92, 44, 86, 38, 85, 14, 78, 41, 103 ), ( 2, 59, 15, 80, 31, 99, 42, 105, 47, 81, 9, 60 ), ( 52, 110, 41, 103, 27, 68, 8, 69, 22, 81, 47, 101 ), ( 18, 65, 5, 58, 7, 72, 26, 73, 9, 81, 22, 94 ), ( 7, 67, 30, 98, 49, 109, 55, 106, 51, 107, 36, 72 ), ( 31, 95, 21, 89, 55, 109, 50, 75, 11, 83, 43, 99 ), ( 27, 97, 45, 96, 50, 109, 49, 85, 38, 87, 19, 68 ), ( 9, 60, 14, 85, 49, 98, 48, 100, 54, 97, 45, 73 ), ( 47, 101, 34, 106, 55, 89, 35, 71, 20, 67, 30, 105 ), ( 22, 94, 28, 75, 50, 96, 23, 90, 40, 95, 21, 69 ). The automorphism group of this embedding is cyclic of order 3, generated by the automorphism inducing the permutation r = (1, 33, 46)(2, 52, 18)(3, 10, 24)(4, 17, 13)(5, 15, 41)(6, 53, 32) (7, 31, 27)(8, 26, 42)(9, 47, 22)(11, 38, 51)(12, 44, 16) (14, 34, 28)(19, 36, 43)(20, 40, 54)(21, 45, 30)(23, 48, 35) (25, 39, 29)(49, 55, 50)(56, 91, 84)(57, 74, 93)(58, 80, 103) (59, 110, 65)(60, 101, 94)(62, 86, 77)(64, 82, 92)(66, 102, 104) (67, 95, 97)(68, 72, 99)(69, 73, 105)(70, 79, 78)(71, 90, 100) (75, 85, 106)(76, 108, 88)(83, 87, 107)(89, 96, 98). ========================================================================= The Ljubljana graph =================== This is the third smallest semi-symmetric cubic graph. It is believed to have been first found by R.M. Foster in the 1970s, and was rediscovered by others later. Number of vertices = 112 Number of edges = 168 Diameter = 8 Girth = 10 Automorphism group of order 168 Vertex-transitive? False Edge-transitive? True Arc-transitive? False Minimum genus orientable embedding ================================== Minimum orientable genus = 13 Number of faces = 32 Face lengths: 24 of length 10, and 8 of length 12 Euler characteristic = -24 Faces: ( 1, 57, 2, 61, 18, 91, 35, 79, 11, 59 ), ( 36, 81, 13, 64, 3, 62, 9, 76, 12, 80 ), ( 43, 78, 10, 74, 26, 75, 45, 100, 24, 72 ), ( 50, 103, 26, 74, 17, 68, 31, 104, 51, 93 ), ( 1, 58, 3, 64, 27, 82, 14, 65, 4, 57 ), ( 43, 72, 8, 61, 2, 60, 6, 70, 29, 98 ), ( 36, 80, 41, 69, 21, 96, 53, 111, 49, 90 ), ( 50, 93, 21, 69, 5, 66, 15, 86, 19, 85 ), ( 36, 90, 17, 74, 10, 63, 20, 92, 37, 81 ), ( 43, 98, 27, 64, 13, 88, 46, 110, 34, 78 ), ( 1, 59, 5, 69, 41, 95, 23, 71, 7, 58 ), ( 50, 85, 18, 61, 8, 77, 32, 107, 38, 103 ), ( 6, 60, 12, 76, 33, 106, 40, 84, 16, 67 ), ( 46, 88, 51, 104, 52, 106, 33, 109, 55, 102 ), ( 20, 63, 4, 65, 28, 99, 30, 67, 16, 87 ), ( 45, 75, 11, 79, 40, 106, 52, 83, 39, 108 ), ( 9, 62, 19, 86, 47, 99, 28, 97, 25, 73 ), ( 32, 77, 37, 92, 44, 94, 22, 102, 55, 105 ), ( 23, 95, 34, 110, 56, 112, 48, 87, 16, 84 ), ( 53, 96, 24, 100, 30, 99, 47, 105, 55, 109 ), ( 31, 68, 7, 71, 42, 94, 44, 73, 25, 101 ), ( 14, 82, 38, 107, 54, 112, 56, 108, 39, 89 ), ( 15, 66, 29, 70, 22, 94, 42, 89, 39, 83 ), ( 35, 91, 49, 111, 48, 112, 54, 101, 25, 97 ), ( 2, 57, 4, 63, 10, 78, 34, 95, 41, 80, 12, 60 ), ( 17, 90, 49, 91, 18, 85, 19, 62, 3, 58, 7, 68 ), ( 27, 98, 29, 66, 5, 59, 11, 75, 26, 103, 38, 82 ), ( 21, 93, 51, 88, 13, 81, 37, 77, 8, 72, 24, 96 ), ( 9, 73, 44, 92, 20, 87, 48, 111, 53, 109, 33, 76 ), ( 45, 108, 56, 110, 46, 102, 22, 70, 6, 67, 30, 100 ), ( 32, 105, 47, 86, 15, 83, 52, 104, 31, 101, 54, 107 ), ( 23, 84, 40, 79, 35, 97, 28, 65, 14, 89, 42, 71 ). The automorphism group of this embedding has order 24, and is generated by the two automorphisms inducing the permutations x = (1, 39)(2, 56)(3, 52)(4, 45)(5, 42)(6, 34)(7, 15)(8, 48)(9, 51) (10, 30)(11, 14)(12, 46)(13, 33)(16, 43)(17, 47)(18, 54)(19, 31) (20, 24)(21, 44)(22, 41)(23, 29)(25, 50)(26, 28)(27, 40)(32, 49) (35, 38)(36, 55)(37, 53)(57, 108)(58, 83)(59, 89)(60, 110) (61, 112)(62, 104)(63, 100)(64, 106)(65, 75)(66, 71)(67, 78) (68, 86)(69, 94)(70, 95)(72, 87)(73, 93)(74, 99)(76, 88) (77, 111)(79, 82)(80, 102)(81, 109)(84, 98)(85, 101)(90, 105) (91, 107)(92, 96)(97, 103) and y = (1, 36, 50)(2, 13, 26)(3, 17, 18)(4, 37, 38)(5, 41, 21)(6, 46, 45) (7, 49, 19)(8, 27, 10)(9, 31, 35)(11, 12, 51)(14, 20, 32) (15, 23, 53)(16, 55, 39)(22, 56, 30)(24, 29, 34)(28, 44, 54) (33, 52, 40)(42, 48, 47)(57, 81, 103)(58, 90, 85)(59, 80, 93) (60, 88, 75)(61, 64, 74)(62, 68, 91)(63, 77, 82)(65, 92, 107) (66, 95, 96)(67, 102, 108)(70, 110, 100)(71, 111, 86)(72, 98, 78) (73, 101, 97)(76, 104, 79)(83, 84, 109)(87, 105, 89)(94, 112, 99). This embedding is reflexible, with x reversing orientation. Minimum genus non-orientable embedding ====================================== Minimum non-orientable genus = 27 Number of faces = 31 Face lengths: 22 of length 10, plus 8 of length 12, and one of length 20 Euler characteristic = -25 Faces: ( 1, 57, 2, 61, 18, 91, 35, 79, 11, 59 ), ( 36, 81, 13, 64, 3, 62, 9, 76, 12, 80 ), ( 43, 78, 10, 74, 26, 75, 45, 100, 24, 72 ), ( 50, 103, 26, 74, 17, 68, 31, 104, 51, 93 ), ( 1, 58, 3, 64, 27, 82, 14, 65, 4, 57 ), ( 43, 72, 8, 61, 2, 60, 6, 70, 29, 98 ), ( 36, 80, 41, 69, 21, 96, 53, 111, 49, 90 ), ( 50, 93, 21, 69, 5, 66, 15, 86, 19, 85 ), ( 36, 90, 17, 74, 10, 63, 20, 92, 37, 81 ), ( 43, 98, 27, 64, 13, 88, 46, 110, 34, 78 ), ( 1, 59, 5, 69, 41, 95, 23, 71, 7, 58 ), ( 50, 85, 18, 61, 8, 77, 32, 107, 38, 103 ), ( 6, 60, 12, 76, 33, 106, 40, 84, 16, 67 ), ( 46, 88, 51, 104, 52, 106, 33, 109, 55, 102 ), ( 20, 63, 4, 65, 28, 99, 30, 67, 16, 87 ), ( 45, 75, 11, 79, 40, 106, 52, 83, 39, 108 ), ( 9, 62, 19, 86, 47, 99, 28, 97, 25, 73 ), ( 32, 77, 37, 92, 44, 94, 22, 102, 55, 105 ), ( 23, 95, 34, 110, 56, 112, 48, 87, 16, 84 ), ( 53, 96, 24, 100, 30, 99, 47, 105, 55, 109 ), ( 31, 68, 7, 71, 42, 94, 44, 73, 25, 101 ), ( 15, 66, 29, 70, 22, 94, 42, 89, 39, 83 ), ( 2, 57, 4, 63, 10, 78, 34, 95, 41, 80, 12, 60 ), ( 17, 90, 49, 91, 18, 85, 19, 62, 3, 58, 7, 68 ), ( 27, 98, 29, 66, 5, 59, 11, 75, 26, 103, 38, 82 ), ( 21, 93, 51, 88, 13, 81, 37, 77, 8, 72, 24, 96 ), ( 9, 73, 44, 92, 20, 87, 48, 111, 53, 109, 33, 76 ), ( 45, 108, 56, 110, 46, 102, 22, 70, 6, 67, 30, 100 ), ( 32, 105, 47, 86, 15, 83, 52, 104, 31, 101, 54, 107 ), ( 23, 84, 40, 79, 35, 97, 28, 65, 14, 89, 42, 71 ), ( 14, 82, 38, 107, 54, 112, 48, 111, 49, 91, 35, 97, 25, 101, 54, 112, 56, 108, 39, 89 ). The automorphism group of this embedding is trivial. =========================================================================