Premium
Hamiltonian embeddings from triangulations
Author(s) -
Grannell Mike J.,
Griggs Terry S.,
Širáň Jozef
Publication year - 2007
Publication title -
bulletin of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 2.396
H-Index - 48
eISSN - 1469-2120
pISSN - 0024-6093
DOI - 10.1112/blms/bdm021
Subject(s) - mathematics , embedding , hamiltonian (control theory) , hamiltonian path , combinatorics , exponential function , pure mathematics , mathematical physics , mathematical analysis , graph , computer science , mathematical optimization , artificial intelligence
A Hamiltonian embedding of K n is an embedding of K n in a surface, which may be orientable or non‐orientable, in such a way that the boundary of each face is a Hamiltonian cycle. Ellingham and Stephens recently established the existence of such embeddings in non‐orientable surfaces for n = 4 and n ⩾ 6. Here we present an entirely new construction which produces Hamiltonian embeddings of K n from triangulations of K n when n ≡ 0 or 1 (mod 3). We then use this construction to obtain exponential lower bounds for the numbers of nonisomorphic Hamiltonian embeddings of K n .