Generalized Cayley maps and Hamiltonian maps of complete graphs

作者：Abas Marcel^*

来源：Discrete Mathematics, 2012, 312(6): 1106-1116.

DOI：10.1016/j.disc.2011.11.028

• Complete graph
• Embedding of graph
• Cayley map
• Hamiltonian map
• Uniform face length

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 k(n) such that the embedding is a Cayley map and that there is no n-gonal Cayley map of K-n if n >= 5 is a prime. In addition, we show that there is no Hamiltonian Cayley map of K-n if n = p(e), p an odd prime and e > 1.

• 出版日期2012-3-28