Interchange graphs and the Hamiltonian cycle polytope (Q1382266)

The author answers the question of adjacency for the whole spectrum of Hamiltonian cycles on the Hamiltonian cycle polytope (HC-polytope, also called the travelling salesman polytope). The \(k\)-interchange graph is the graph with the Hamiltonian cycles of \(K_n\) as vertices, and an edge between two vertices if and only if the corresponding Hamiltonian cycles differ in an interchange of \(k\) edges. It is shown that the 2- and 3-interchange graphs are the only ones that are subgraphs of the skeleton of the HC-polytope, and the \((n-1)\)- and \(n\)-interchange graphs are the only ones that do not have edges in common with the skeleton. For each \(k\) such that \(4\leq k\leq n-2\) there are Hamiltonian cycles that are adjacent and cycles that are nonadjacent in the skeleton. The Hamiltonicity of \(k\)-intersecting graphs is solved for several values of \(k\).