✦ LIBER ✦

On the number of Hamiltonian cycles in triangulations

✍ Scribed by Jan Kratochvil; Dainis Zeps

Publisher: John Wiley and Sons
Year: 1988
Tongue: English
Weight: 185 KB
Volume: 12
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190120209

No coin nor oath required. For personal study only.

✦ Synopsis

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 triangulation on n vertices is four. We also show that this theorem holds for triangulations of arbitrary surfaces and for 3-connected triangulated graphs.

1. PRELIMINARY

In 1978, E. Grinberg [ l ] found examples of 3-connected (nonplanar) graphs with exactly one Harniltonian cycle and he asked whether a planar graph of this property exists. In 198 1. L. S . Melnikov [personal communication] asked a more special question, whether there exists a planar triangulation with exactly one Hamiltonian cycle (different from the trivial example K?). In the sequel, the negative answer to thc latter question is proved. Moreover. we show that a Hamiltonian planar triangulation on more than four vertices has at least four Hamiltonian cycles. This provides a solution of the main problem asked in [ 2 ] , where it is shown that, for every n 2 12, there exists a planar triangulation on n vertices containing exactly four Harniltonian cycles. We extend our result to triangulations of arbitrary surfaces and to (vertex-)3-connected graphs, and more generally to the so-called two-triangle graphs defined below. The proof is based on two propositions; the idea of thc so-called lollipop graphs 14) is used in the proof of Proposition 2.

📜 SIMILAR VOLUMES

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 👁 1 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

Hamiltonian tournaments with the least n

Hamiltonian tournaments with the least number of 3-cycles

✍ M. Burzio; D. C. Demaria 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 416 KB

## Abstract We characterize the family of hamiltonian tournaments with the least number of 3‐cycles, studying their structure and their score sequence. Furthermore, we obtain the number of nonisomorphic tournaments of this family.

Hamiltonian cycles in bipartite quadrang

Hamiltonian cycles in bipartite quadrangulations on the torus

✍ Atsuhiro Nakamoto; Kenta Ozeki 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 133 KB

## 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 th

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 the Interval Number of a Triangulated

On the Interval Number of a Triangulated Graph

✍ Thomas Andreae 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 414 KB

The interval number of a simple undirected graph G, denoted i(G), is the least nonnegative integer r for which we can assign to each vertex in G a collection of at most r intervals on the real line such that two distinct vertices u and w of G are adjacent if and only if some interval for u intersect

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

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