HAMILTONIAN CIRCUITS AND PATHS IN SUBSET GRAPHS WITH CIRCULAR ADJACENCY

Consider the subset graph G(n,k) whose vertex set C(n,k) is the set of all n-tuples of '0's' and '1's' with exactly k '1's'. Let an edge exi st between two vertices a and b in G(n,k) if and only if a can be tran sformed into b by the interchange of two adjacent coordinate values, w ith the first and last coordinates considered adjacent. This paper sho ws 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 co des' of C (n, k).