The spurs of D. H. Lehmer : Hamiltonian paths in neighbor-swap graphs of permutations

    Research output: Contribution to journalArticleAcademicpeer-review

    46 Downloads (Pure)

    Abstract

    Consider the graph with all permutations of a symbol sequence as vertices, where two permutations are connected by an edge when they differ by an interchange of two distinct adjacent symbols. In 1965, D. H. Lehmer conjectured that all vertices in this graph can be visited by a Hamiltonian path that is possibly imperfect, in the sense of having spurs. Such a spur visits a vertex twice, with a single vertex in-between. We prove Lehmer’s conjecture for binary permutations that involve only two distinct symbols. For general symbol sequences, we identify the stutter permutations as candidate spur tips, and prove that the non-stutter permutations admit a disjoint cycle cover. We also provide new (simpler) proofs for some known results.

    Original languageEnglish
    Pages (from-to)295-310
    Number of pages16
    JournalDesigns, Codes and Cryptography
    Volume84
    Issue number1-2
    Early online date14 Nov 2016
    DOIs
    Publication statusPublished - 1 Jul 2017

    Keywords

    • Hamiltonian path
    • Minimal-change generation
    • Permutation

    Fingerprint Dive into the research topics of 'The spurs of D. H. Lehmer : Hamiltonian paths in neighbor-swap graphs of permutations'. Together they form a unique fingerprint.

    Cite this