ABSTRACT
Many problems in combinatorial optimization are modeled by a cycle containing all the vertices of an appropriate graph. For example, if S is a set of cardinality n, then it could be useful to have a listing A1, A2, . . . , A2n of all subsets of S such that there is minimal change from any one subset to the next one in the list. In fact, this can be done so that for each index i, the set Ai+1 (indices modulo 2n) is obtained from Ai by either inserting or deleting a single element of S. The list so created corresponds in a natural way to a cycle in the n-dimensional cube Qn. Such a sequence of binary n-tuples is called a Gray code. We first consider several conditions for a graph to have a spanning cycle. In Section 3.2 we turn our attention to the question of when a Cartesian product of two graphs is hamiltonian. It turns out that the existence of a spanning cycle in a Cartesian product is closely related to the spanning trees of the two factors. We then conclude this chapter in Section 3.3 with a brief study of prisms.
