HYPER-HAMILTON LACEABLE AND CATERPILLAR-SPANNABLE PRODUCT GRAPHS

We define a Hamilton laceable graph G to be hyper-Hamilton laceable (h yper HL) if either (a) G is equitable, and if v is any node of G, then G-v is HL, or (b) G is nearly equitable, and if v is any node in its larger color set, then G-v is HL. In particular, the hypercube Q(n) is hyper HL. A graph G is caterpillar-spannable (CS) if it has a spannin g tree which is a caterpillar. We present several theorems concerning products of CS graphs. It is shown that the product of two CS graphs s uch that at least one of them has maximum degree 3 is CS.