Abstract. A Gray code is an ordering of elements of a given set so that consecutive elements differ just "slightly". If we construct a graph G, whose vertices are the elements of the given set and two elements are joined by an edge whenever they differ just "slightly", then a Gray code is a Hamiltonian path in G. We examine closed Hamiltonian paths (i.e., the Hamiltonian cycles) in G, when the elements are different labellings of a given graph H and the "slight" change consists of changing k edges of H. (The k is a parameter.)