Computing and Sampling Restricted Vertex Degree Subgraphs and Hamiltonian Cycles

Details Computing and Sampling Restricted Vertex Degree Subgraphs and Hamiltonian Cycles Computing and Sampling Restricted Vertex Degree Subgraphs and Hamiltonian Cycles

2000-08-31

arxiv.org/abs/math/0008231v2

Mathematics

Combinatorics

42 pages, fifteen figures, includes new references

Scientific paper

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: V \mapsto \mathbb Z^+$, $S_{\phi}$ is the set of subgraphs of $G$ in which each $v\in V$ 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$.

Affiliated with

Also associated with

No associations

Rating

Computing and Sampling Restricted Vertex Degree Subgraphs and Hamiltonian Cycles does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Computing and Sampling Restricted Vertex Degree Subgraphs and Hamiltonian Cycles, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing and Sampling Restricted Vertex Degree Subgraphs and Hamiltonian Cycles will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-268316