Hyper-Hamilton Laceable and Caterpillar-Spannable Product Graphs
We define a Hamilton laceable graph G to be hyper-Hamilton laceable (hyper 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 Qn is hyper HL. A graph G is caterpillar-spannable (CS) if it has a spanning tree which is a caterpillar. We present several theorems concerning products of CS graphs. It is shown that the product of two CS graphs such that at least one of them has maximum degree 3 is CS.
hyper-hamilton laceable hamilton laceable caterpillar equitable hamiltonian