✦ LIBER ✦

On the maximum number of cycles in a planar graph

✍ Scribed by R. E. L. Aldred; Carsten Thomassen

Publisher: John Wiley and Sons
Year: 2008
Tongue: English
Weight: 142 KB
Volume: 57
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20290

No coin nor oath required. For personal study only.

✦ Synopsis

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 possible in the sense that any prism, that is, the Cartesian product of a cycle and a path with one edge, has more than 2^r − 1^ cycles. © Wiley Periodicals, Inc. J. Graph Theory 57: 255–264, 2008

📜 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

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 the vertex face total chromatic numbe

On the vertex face total chromatic number of planar graphs

✍ Weifan, Wang; Jiazhuang, Liu 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 471 KB 👁 2 views

Let G be a planar graph. The vertex face total chromatic number ,y13(G) of G is the least number of colors assigned to V(G) U F(G) such that no adjacent or incident elements receive the same color. The main results of this paper are as follows: (1) We give the vertex face total chromatic number for

The number of shortest cycles and the ch

The number of shortest cycles and the chromatic uniqueness of a graph

✍ C. P. Teo; K. M. Koh 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 403 KB

## Abstract For a graph __G__, let __g__(__G__) and σ~g~(__G__) denote, respectively, the girth of __G__ and the number of cycles of length __g__(__G__) in __G__. In this paper, we first obtain an upper bound for σ~g~(__G__) and determine the structure of a 2‐connected graph __G__ when σ~g~(__G__)

On the asymptotic behavior of the maximu

On the asymptotic behavior of the maximum number of spanning trees in circulant graphs

✍ Lonc, Zbigniew; Parol, Krzysztof; Wojciechowski, Jacek M. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 126 KB 👁 3 views

The following asymptotic estimation of the maximum number of spanning trees f k (n) in 2kregular circulant graphs ( k ú 1) on n vertices is the main result of this paper: )) , where

The upper bound of the number of cycles

The upper bound of the number of cycles in a 2-factor of a line graph

✍ Jun Fujisawa; Liming Xiong; Kiyoshi Yoshimoto; Shenggui Zhang 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 183 KB

## Abstract Let __G__ be a simple graph with order __n__ and minimum degree at least two. In this paper, we prove that if every odd branch‐bond in __G__ has an edge‐branch, then its line graph has a 2‐factor with at most ${{3n - 2}\over {8}}$ components. For a simple graph with minimum degree at le