𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the Maximum Number of Cycles in Outerplanar and Series–Parallel Graphs

✍ Scribed by Anna de Mier; Marc Noy

Publisher
Springer Japan
Year
2011
Tongue
English
Weight
170 KB
Volume
28
Category
Article
ISSN
0911-0119

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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 Maximum Number of Independent Cyc
On the Maximum Number of Independent Cycles in a Bipartite Graph
✍ Hong Wang 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 404 KB

Let G=(V 1 , V 2 ; E ) be a bipartite graph with |V 1 |= |V 2 | =n 2k, where k is a positive integer. Suppose that the minimum degree of G is at least k+1. We show that if n>2k, then G contains k vertex-disjoint cycles. We also show that if n=2k, then G contains k&1 quadrilaterals and a path of orde

The circular chromatic number of series-
The circular chromatic number of series-parallel graphs
✍ Hell, Pavol; Zhu, Xuding 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 238 KB 👁 2 views

In this article, we consider the circular chromatic number χ c (G) of series-parallel graphs G. It is well known that series-parallel graphs have chromatic number at most 3. Hence, their circular chromatic numbers are at most 3. If a seriesparallel graph G contains a triangle, then both the chromati

The number of edges in a maximum cycle—d
The number of edges in a maximum cycle—distributed graph
✍ Yongbing Shi 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 288 KB

Shi, Y., The number of edges in a maximum cycle-distributed graph, Discrete Mathematics 104 (1992) 205-209. Let f(n) (f\*(n)) be the maximum possible number of edges in a graph (2-connected simple graph) on n vertices in which no two cycles prove that, for every integer n > 3, f(n) 3 n + k + [i( [~(

On the maximum number of pairwise compat
On the maximum number of pairwise compatible euler cycles
✍ H. Fleischner; A. J. W. Hilton; Bill Jackson 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 629 KB

## Abstract B. Jackson [4] made the following conjecture: If __G__ is an Eulerian graph with δ(__G__) ≥ 2__k__, then __G__ has a set of 2__k__ ‐ 2 pairwise compatible Euler cycles (i.e., every pair of adjacent edges appears in at most one of these Euler cycles as a pair of consecutive edges). We ve