Regular orientable embeddings of complete bipartite graphs

Abstract

In this paper, it will be shown that the isomorphism classes of regular orientable embeddings of the complete bipartite graph K-n,K-n are in one-to-one correspondence with the permutations on n elements satisfying a given criterion, and the isomorphism classes of them are completely classified when n is a product of any two (not necessarily distinct) prime numbers. For other n, a lower bound of the number of those isomorphism classes of K-n,K-n is obtained. As a result, many new regular orientable embeddings of the complete bipartite graph are constructed giving an answer of Nedela-Skoviera's question raised in [12]. (c) 2005 Wiley Periodicals, Inc.