Computing and Sampling Restricted Vertex Degree Subgraphs and Hamiltonian Cycles

MaRDI QIDQ6470583zbMATH OpenFDO

Authors Scott Sheffield

Publication date 30 August 2000

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45)

Abstract: 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 $phi:Vmapstomathbb{Z}^{+}$, $S_{phi}$ is the set of subgraphs of $G$ in which each $vinV$ has degree $phi(v)$. Two elements of $S_{phi}$ are said to be adjacent if they differ by a $Z$-transformation. We determine the connected components of $S_{phi}$ and assign a {it height function} to each of its elements. If $phi$ is identically two, and $G$ is a grid graph, $S_{phi}$ 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$.

This page was built for publication: Computing and Sampling Restricted Vertex Degree Subgraphs and Hamiltonian Cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6470583)