✦ LIBER ✦

On the number of hamiltonian cycles in a maximal planar graph

✍ Scribed by S. L. Hakimi; E. F. Schmeichel; C. Thomassen

Publisher: John Wiley and Sons
Year: 1979
Tongue: English
Weight: 243 KB
Volume: 3
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190030407

No coin nor oath required. For personal study only.

✦ Synopsis

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 prove that every 4‐connected maximal planar graph on p vertices contains at least p/(log~2~ p) Hamiltonian cycles.

📜 SIMILAR VOLUMES

On the number of cycles of length 4 in a

On the number of cycles of length 4 in a maximal planar graph

✍ Ahmad Fawzi Alameddine 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 148 KB

## Abstract Let __p__ and __C__~4~ (__G__) be the number of vertices and the number of 4‐cycles of a maximal planar graph __G__, respectively. Hakimi and Schmeichel characterized those graphs __G__ for which __C__~4~ (__G__) = 1/2(__p__^2^ + 3__p__ ‐ 22). This characterization is correct if __p__ ≥

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 maximum number of cycles in a pla

On the maximum number of cycles in a planar graph

✍ R. E. L. Aldred; Carsten Thomassen 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 142 KB

## Abstract Let __G__ be a graph on __p__ vertices with __q__ edges and let __r__ = __q__ − __p__ = 1. We show that __G__ has at most ${15\over 16} 2^{r}$ cycles. We also show that if __G__ is planar, then __G__ has at most 2^__r__ − 1^ = __o__(2^__r__ − 1^) cycles. The planar result is best possib

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

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

Uniqueness of maximal dominating cycles

Uniqueness of maximal dominating cycles in 3-regular graphs and of hamiltonian cycles in 4-regular graphs

✍ Herbert Fleischner 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 461 KB

## Abstract We construct 3‐regular (cubic) graphs __G__ that have a dominating cycle __C__ such that no other cycle __C__~1~ of __G__ satisfies __V(C)__ ⊆ __V__(__C__~1~). By a similar construction we obtain loopless 4‐regular graphs having precisely one hamiltonian cycle. The basis for these const

On the connectivity of maximal planar gr

On the connectivity of maximal planar graphs

✍ S. L. Hakimi; E. F. Schmeichel 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 254 KB