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, Springer-Verlag, Berlin, 1974.


Submitted by: Arthur White

Send comments to dan.archdeacon@uvm.edu

December, 2003