Hamiltonian circuits and paths in subset graphs with circular adjacency (Q1313856)

Let \(G(n,k)\) be the graph whose vertex set is the set of all binary \(n\)- tuples with exactly \(k\) 1's and for which an edge exists between two such vertices if and only if one vertex can be transformed into the other by the interchange of two adjacent coordinate values (with the first and last coordinates considered adjacent). The following results are obtained. Theorem 1. A Hamiltonian circuit exists for \(G(n,k)\) if and only if the following conditions hold: (a) both \(n\) and \(k\) are even, and (b) \(n \geq 7\) and \(k = 2\) or \(n - 2\). Theorem 2. The graph \(G(n,k)\) has a Hamiltonian path if and only if \(n\) and \(k\) are not both even.