2000/08/31 by Scott Sheffield, Sheffield, Scott
Mathematics · #05C45 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #math.CO #math.PR #msc:05C45
paper · pdf · doi:10.48550/arxiv.math/0008231
42 pages, fifteen figures, includes new references
arxiv created 2001/02/27 · arxiv updated 2009/11/30
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 boundary edges of a single face---and if each subgraph contains an alternating set of the edges of that face. For a given ϕ: V ↦ \mathbb Z+, Sϕ is the set of subgraphs of G in which each v∈ V has degree ϕ(v). Two elements of Sϕ are said to be adjacent if they differ by a Z-transformation. We determine the connected components of Sϕ and assign a \it height function to each of its elements. If ϕ is identically two, and G is a grid graph, Sϕ contains the partitions of the vertices of G into cycles. We prove that we can always apply a series of Z-transformations to decrease the total number of cycles provided there is enough ``slack'' in the corresponding height function. This allows us to determine in polynomial time the minimal number of cycles into which G can be partitioned provided G has a limited number of non-square faces. In particular, we determine the Hamiltonicity of polyomino graphs in O(|V|2) steps. The algorithm extends to n-holed-torus-embedded graphs that have grid-like properties. We also provide Markov chains for sampling and approximately counting the Hamiltonian cycles of G.