Interchange graphs and the Hamiltonian cycle polytope (Q1382266)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Interchange graphs and the Hamiltonian cycle polytope |
scientific article |
Statements
Interchange graphs and the Hamiltonian cycle polytope (English)
0 references
14 September 1998
0 references
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\).
0 references
\(k\)-interchange graph
0 references
adjacency
0 references
Hamiltonian cycles
0 references
Hamiltonian cycle polytope
0 references
travelling salesman polytope
0 references
Hamiltonicity
0 references