Generalized Cayley maps and Hamiltonian maps of complete graphs

摘要

A cellular embedding of a connected graph G is said to be Hamiltonian if every face of the embedding is bordered by a Hamiltonian cycle (a cycle containing all the vertices of G) and it is an m-gonal embedding if every face of the embedding has the same length m. In this paper, we establish a theory of generalized Cayley maps, including a new extension of voltage graph techniques, to show that for each even n there exists a Hamiltonian embedding of ~(Kn) such that the embedding is a Cayley map and that there is no n-gonal Cayley map of ~(Kn) if n<5 is a prime. In addition, we show that there is no Hamiltonian Cayley map of ~(Kn) if n= ~(pe), p an odd prime and e>1.