Regular Embeddings of Canonical Double Coverings of Graphs

✍ Scribed by Roman Nedela; Martin Škoviera

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 792 KB
• Volume: 67
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.1996.0044

✦ Synopsis

This paper addresses the question of determining, for a given graph G, all regular maps having G as their underlying graph, i.e., all embeddings of G in closed surfaces exhibiting the highest possible symmetry. We show that if G satisfies certain natural conditions, then all orientable regular embeddings of its canonical double covering, isomorphic to the tensor product G K 2 , can be described in terms of regular embeddings of G. This allows us to lift'' the classification of regular embeddings of a given graph to a similar classification for its canonical double covering and to establish various properties of the derived'' maps by employing those of the ``base'' maps. We apply these results to determining all orientable regular embeddings of the tensor products K n K 2 (known as the cocktail-party graphs) and of the n-dipoles D n , the graphs consisting of two vertices and n parallel edges joining them. In the first case we show, in particular, that regular embeddings of K n K 2 exist only if n is a prime power p l , and there are 2,(n&1) or ,(n&1) isomorphism classes of such maps (where , is Euler's function) according to whether l is even or odd. For l even an interesting new infinite family of regular maps is discovered. In the second case, orientable regular embeddings of D n exist for each positive integer n, and their number is a power of 2 depending on the decomposition of n into primes.