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
    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

    Identifiers