Premium
Pairs of Adjacent Hamiltonian Circuits with Small Intersection
Author(s) -
West Douglas B.
Publication year - 1978
Publication title -
studies in applied mathematics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 46
eISSN - 1467-9590
pISSN - 0022-2526
DOI - 10.1002/sapm1978593245
Subject(s) - hamiltonian (control theory) , mathematics , electronic circuit , polytope , combinatorics , hamiltonian path , intersection (aeronautics) , regular polygon , connection (principal bundle) , travelling salesman problem , discrete mathematics , topology (electrical circuits) , geometry , algorithm , graph , physics , mathematical optimization , quantum mechanics , engineering , aerospace engineering
Consider the question: When can the edges in a pair of Hamiltonian circuits be redistributed to form another pair of circuits with the same union and intersection? A class of pairs is exhibited which intersect in two edges and cannot be rearranged in this way. A connection to algorithms for the traveling salesman problem is explained using the convex polytope of Hamiltonian circuits in . The exhibited pair is shown to be an edge of that polytope.