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${}^{\ast }$ $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.