✦ LIBER ✦

Hamiltonian cycles in bipartite quadrangulations on the torus

✍ Scribed by Atsuhiro Nakamoto; Kenta Ozeki

Publisher: John Wiley and Sons
Year: 2011
Tongue: English
Weight: 133 KB
Volume: 69
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20569

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

In this article, we shall prove that every bipartite quadrangulation G on the torus admits a simple closed curve visiting each face and each vertex of G exactly once but crossing no edge. As an application, we conclude that the radial graph of any bipartite quadrangulation on the torus has a hamiltonian cycle. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 69:143‐151, 2012

📜 SIMILAR VOLUMES

Alternating hamiltonian cycles in two co

Alternating hamiltonian cycles in two colored complete bipartite graphs

✍ A. G. Chetwynd; A. J. W. Hilton 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 269 KB 👁 1 views

## Abstract We give necessary and sufficient conditions for the existence of an alternating Hamiltonian cycle in a complete bipartite graph whose edge set is colored with two colors.

On 4-cycles in random bipartite tourname

On 4-cycles in random bipartite tournaments

✍ Béla Bollobés; Ove Frank; Michał KarońSki 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 413 KB

We consider a random rn by n bipartite tournament T, , consisting of rnn independent random arcs which have a common probability p of being directed from the rn part to the n part. We determine the expected value and variance of the number of 4-cycles in T,,,, and the probability that T, , has no cy

On the number of Hamiltonian cycles in t

On the number of Hamiltonian cycles in triangulations

✍ Jan Kratochvil; Dainis Zeps 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 185 KB 👁 2 views

It is proved that if a planar triangulation different from K3 and K4 contains a Hamiltonian cycle, then it contains at least four of them. Together with the result of Hakimi, Schmeichel, and Thomassen [21, this yields that, for n 2 12, the minimum number of Hamiltonian cycles in a Hamiltonian planar

On certain Hamiltonian cycles in planar

On certain Hamiltonian cycles in planar graphs

✍ B�hme, T.; Harant, J.; Tk�?, M. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 162 KB 👁 2 views

The problem is considered under which conditions a 4-connected planar or projective planar graph has a Hamiltonian cycle containing certain prescribed edges and missing certain forbidden edges. The results are applied to obtain novel lower bounds on the number of distinct Hamiltonian cycles that mus

On hamiltonian cycles in the prism over

On hamiltonian cycles in the prism over the odd graphs

✍ Letícia R. Bueno; Peter Horák 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 137 KB 👁 2 views

The Kneser graph K (n, k) has as its vertex set all k-subsets of an n-set and two k-subsets are adjacent if they are disjoint. The odd graph O k is a special case of Kneser graph when n = 2k +1. A long standing conjecture claims that O k is hamiltonian for all k>2. We show that the prism over O k is

On the number of hamiltonian cycles in a

On the number of hamiltonian cycles in a maximal planar graph

✍ S. L. Hakimi; E. F. Schmeichel; C. Thomassen 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 243 KB 👁 2 views

## Abstract We consider the problem of the minimum number of Hamiltonian cycles that could be present in a Hamiltonian maximal planar graph on __p__ vertices. In particular, we construct a __p__‐vertex maximal planar graph containing exactly four Hamiltonian cycles for every __p__ ≥ 12. We also pro