Hamiltonian cycles and chains in graphs with striped and circulant distance matrices : theory and applications

This work was motivated by the work of Garfinkel who formulated the problem of wallpapering a room so as to minimize the paper wasted as a traveling salesman problem over a very special class of distance matrices. In this work a much more realistic version of the wallpapering problem, obtained by relaxing many of the restrictive assumptions of Grafinkel's work, is addressed.

This work also addresses some very special classes of the Hamiltonian cycle problem. Stripe k of an n-node graph is the set of arcs (i,j) such that j - i = k(mod n). Let graph G = (N,A) where the node set N has cardinality n and the arc set A contains all arcs of k different stripes, say s₁, s₂,..., s_k. The k-stripe problem addresses the question, "Does graph G contain a h-cycle?" In this work, this problem is fully solved for k = 2 and some special cases of the problem for k = 3 are also solved. Further, it is shown that a special case of the 3-stripe problem solves the bottleneck version of the wallpaper problem addressed by Garfinkel.