✦ LIBER ✦

Bounds on the number of cycles of length three in a planar graph

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

Book ID: 112885405
Publisher: The Hebrew University Magnes Press
Year: 1982
Tongue: English
Weight: 760 KB
Volume: 41
Category: Article
ISSN: 0021-2172
DOI: 10.1007/bf02760664

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On the number of cycles of length k in a

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

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

Let G be a maximal planar graph with p vertices, and let Ck(G) denote the number of cycles of length k in G. We first present tight bounds for C,(G) and C,(G) in terms of p. We then give bounds for Ck(G) when 5 5 k 5 p , and consider in particular bounds for C,(G), in terms of p. Some conjectures an

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 👁 2 views

## 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 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 👁 2 views

## 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 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 👁 3 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

A Bound on the Chromatic Number of an Al

A Bound on the Chromatic Number of an Almost Planar Graph

✍ Nenashev, G. V. 📂 Article 📅 2014 🏛 Springer US 🌐 English ⚖ 296 KB

A bound on the chromatic number of the s

A bound on the chromatic number of the square of a planar graph

✍ Michael Molloy; Mohammad R. Salavatipour 📂 Article 📅 2005 🏛 Elsevier Science 🌐 English ⚖ 346 KB