A Surprising Regularity in the Number of Hamilton Paths in Polygonal Bigraphs

Abstract

The smallest bigraph that is edge-critical but not edge-minimal with respect to Hamilton laceability is the Franklin graph. Polygonal bigraphs\(^*\) \(P_{m,}\), which generalize one of the many symmetries of the Franklin graph, share this property of being edge-critical but not edge-minimal \([1]\). An enumeration of Hamilton paths in \(P_{m}\) for small \(m\) reveals surprising regularities: there are \(2^m\) Hamilton paths between every pair of adjacent vertices, \(3 \times 2^{m-2}\) between every vertex and a unique companion vertex, and \(3 \times 2^{m-2}\) between all other pairs. Notably, Hamilton laceability only requires at least one Hamilton path between every pair of vertices in different parts; remarkably, there are exponentially many.