The Genus of a Complete
Graph Minus a Hamiltonian Cycle
Let K_n – C_n denote the complete graph minus the edges of a Hamiltonian cycle. Art White asks:
Conjecture: What is the orientable genus of K_n – C_n
The conjectured value would be given by the embedding as close to a triangulation as possible, namely ceiling[(n^2-9n+12)/12] (with possible small exceptions). White reports the following observations:
1) the genus is non-decreasing in n
2) the graph is non-planar for n at most 6
3) the conjectured bound fails for n = 7
4) the conjecture is true for n = 8,9
5) current graph constructions may be useful (see [R])
The problem was apparently suggested to Art White by Mike Plummer, but I do
not know why he was interested.
References:
[R] G. Ringel, Map Color Theeorem,
Submitted by: Arthur White
Send comments to dan.archdeacon@uvm.edu
December, 2003