Embeddings of Small Graphs on the Torus
Andrei Gagarin, William Lawrence Kocay, Daniel Neilson · CUBO, A Mathematical Journal · 2003
Embeddings of graphs on the torus are studied. All 2-cell embeddings of the vertex-transitive graphs on 12 vertices or less are constructed. Their automorphism groups and dual maps are also constructed. A table of embeddings is presented. 1. Toroidal Graphs Let G be a 2-connected graph. The vertex and edge sets of G are V (G) and E(G), respectively. E(G) is a multiset consisting of unordered pairs {u,v}, where u,v 2 V (G), and possibly ordered pairs (v,v), as the graphs G will sometimes have multiple edges and/or loops. We write the pair {u,v} as uv, and the ordered pair (v,v) as vv, which represents a loop on vertex v. If u,v 2 V (G) then u ! v means that u is adjacent to v (and so also v ! u). The reader is referred to Bondy and Murty [2], West [11], or Gross and Tucker [3] for other graph-theoretic terminology. An embedding of a graph on a surface is represented combinatorially by a rotation system [3]. This consists of a cyclic ordering of the incident edges, for each vertex v. Let v be a vertex of G, incident on edges e1,e2,...,ek. We write v ! (e1,e2,...,ek) to indicate the cyclic ordering for v in a rotation system. If some ei is a loop vv, then this loop must appear twice in the cyclic adjacency list (e1,e2,...,ek), because walking around the vertex v along a small circle in the torus will require that a loop vv be crossed twice. Thus, we assume that if ei is a loop vv, there is another e 0 in the list corresponding to the same loop vv. Since every loop must appear twice in the rotation system, a loop contributes two to the degree of a vertex. If ei with endpoints uv is not a loop, then it will appear in the cyclic adjacency list of both vertices u and v. Given ei in the list for u, the corresponding ej in the list for v is given by the rotation sytem. Figure 1 shows an embedding of the complete