Interchange graphs and the Hamiltonian cycle polytope
type: Item
instance of: scholarly article
title: Interchange graphs and the Hamiltonian cycle polytope
zbMATH Open document ID: 0895.05040
DOI: 10.1016/S0166-218X(97)00086-3
author: Gerard Sierksma
published in: Discrete Applied Mathematics
publication date: 1998-09-14T00:00:00Z
full work available at URL: dam
review text: 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\).
reviewed by: E. J. F. Primrose
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 1133162
zbMATH Keywords: \(k\)-interchange graph
zbMATH Keywords: adjacency
zbMATH Keywords: Hamiltonian cycles
zbMATH Keywords: Hamiltonian cycle polytope
zbMATH Keywords: travelling salesman polytope
zbMATH Keywords: Hamiltonicity
MaRDI profile type: Publication
cites work: Q3941433
cites work: Q3714900
cites work: Q3882177
cites work: Hamiltonicity and combinatorial polyhedra
cites work: Hamiltonicity in (0-1)-polyhedra
cites work: The adjacency relation on the traveling salesman polytope is NP-Complete
cites work: The skeleton of the symmetric Traveling Salesman Polytope
cites work: Hamiltonicity and the 3-Opt procedure for the traveling Salesman problem
cites work: Faces with large diameter on the symmetric traveling salesman polytope
cites work: Hamiltonian Cycles and Uniquely Edge Colourable Graphs
OpenAlex ID: W1967722468
description: scientific article; zbMATH DE number 1133162