Hamiltonian circuits and paths in subset graphs with circular adjacency

✍ Scribed by T.C. Enns

• Publisher: Elsevier Science
• Year: 1993
• Tongue: English
• Weight: 751 KB
• Volume: 122
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(93)90292-2

✦ Synopsis

Consider the subset graph G(n, k) whose vertex set C(n, k) is the set of all n-tuples of 'O's' and 'l's' with exactly k 'I's'. Let an edge exist between two vertices a and b in G(n,k) if and only if a can be transformed into b by the interchange of two adjacent coordinate values, with the first and last coordinates considered adjacent. This paper shows that a Hamiltonian circuit exists in G(n, k) if and only if neither n and k are both even, nor k = 2 or n -2 for n > 7. It is also shows that a Hamiltonian path exists in G(n, k) if and only if n and k are not both even. Such Hamiltonian paths and circuits are called 'Gray codes' of C(n, k).