On the Number of Nonisomorphic Orientable Regular Embeddings of Complete Graphs

✍ Scribed by Vladimir P. Korzhik; Heinz-Jurgen Voss

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 260 KB
• Volume: 81
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.2000.1993

✦ Synopsis

In this paper we consider those 2-cell orientable embeddings of a complete graph K n+1 which are generated by rotation schemes on an abelian group 8 of order n+1, where a rotation scheme an 8 is defined as a cyclic permutation ( ; 1 , ; 2 , ..., ; n ) of all nonzero elements of 8. It is shown that two orientable embeddings of K n+1 generated by schemes (; 1 , ; 2 , ..., ; n ) and (# 1 , # 2 , ..., # n ) are isomorphic if and only if (# 1 , # 2 , ..., # n )=(.( ; 1 ), .( ; 2 ), ..., .( ; n )) or (# 1 , # 2 , ..., # n )= (.( ; n ), ..., .( ; 2 ), .( ; 1 )), where . is an automorphism of 8. As a consequence, by representing schemes by index one current graphs, the following results are obtained. The graphs K 12s+4 and K 12s+7 for every s 1 have at least 4 s nonisomorphic face 3-colorable orientable triangular embeddings. The graph K 8s+5 for every s 1 has at least 8_16 s&1 nonisomorphic orientable quadrangular embeddings.