✦ LIBER ✦

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

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

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

No coin nor oath required. For personal study only.

✦ Synopsis

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 and unsolved problems are stated.

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

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

An upper bound on the length of a Hamilt

An upper bound on the length of a Hamiltonian walk of a maximal planar graph

✍ Takao Asano; Takao Nishizeki; Takahiro Watanabe 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 840 KB

## Abstract A Hamiltonian walk of a connected graph is a shortest closed walk that passes through every vertex at least once, and the length of a Hamiltonian walk is the total number of edges traversed by the walk. We show that every maximal planar graph with __p__(≥ 3) vertices has a Hamiltonian c

On the Number of Acute Triangles in a St

On the Number of Acute Triangles in a Straight-Line Embedding of a Maximal Planar Graph

✍ Atsushi Kaneko; Hiroshi Maehara; Mamoru Watanabe 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 80 KB

In this paper we show that any maximal planar graph with m triangles except the unbounded face can be transformed into a straight-line embedding in which at least WmÂ3X triangles are acute triangles. Moreover, we show that any maximal outerplanar graph can be transformed into a straight-line embeddi

On the number of cycles of short length

On the number of cycles of short length in the DE Bruijn-good graph Gn

✍ Zhe-xian Wan; Rong-hua Xiong; Min-an Yu 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 865 KB

An algebraic approach to enumerate the number of cycles of short length in the de Bruijn-Good graph Gn is given and the following theorem is proved. where ~)k,m--1 is defined to be the number of positive integers l <<-k satisfying (k, l) <<-m -1, l~(q) is the M6bius function, dt = (k, l), e~ = 0 or