Computing and Sampling Restricted Vertex Degree Subgraphs and Hamiltonian Cycles

Scott Sheffield

Let $G=(V,E)$ be a bipartite graph embedded in a plane (or $n$-holed torus). Two subgraphs of $G$ differ by a {\it $Z$-transformation} if their symmetric difference consists of the…