Cubic, Edge-Critical, Hamilton Laceable Bigraphs

Abstract

Edge minimal Hamilton laceable bigraphs on \(2m\) vertices have at least \(\left\lfloor \frac{m+3}{6} \right\rfloor\) vertices of degree \(2\). If a bigraph is edge minimal with respect to Hamilton laceability, it is by definition edge critical, meaning the deletion of any edge will cause it to no longer be Hamilton laceable. The converse need not be true. The \(m\)-crossed prisms \([8]\) on \(4m\) vertices are edge critical for \(m \geq 2\) but not edge minimal since they are cubic. A simple modification of \(m\)-crossed prisms forms a family of “sausage” bigraphs on \(4m + 2\) vertices that are also cubic and edge critical. Both these families share the unusual property that they have exponentially many Hamilton paths between every pair of vertices in different parts. Even so, since the bigraphs are edge critical, deleting an arbitrary edge results in at least one pair having none.