✦ LIBER ✦

On The Number Of Sets Of Cycle Lengths

✍ Scribed by Jacques Verstraëte

Publisher: Springer-Verlag
Year: 2004
Tongue: English
Weight: 237 KB
Volume: 24
Category: Article
ISSN: 0209-9683
DOI: 10.1007/s00493-004-0043-6

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Cycle length parities and the chromatic

Cycle length parities and the chromatic number

✍ Christian Löwenstein; Dieter Rautenbach; Ingo Schiermeyer 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 164 KB

## Abstract In 1966 Erdös and Hajnal proved that the chromatic number of graphs whose odd cycles have lengths at most __l__ is at most __l__+1. Similarly, in 1992 Gyárfás proved that the chromatic number of graphs which have at most __k__ odd cycle lengths is at most 2__k__+2 which was originally c

Generalized Sets of Lengths

✍ Scott T Chapman; William W Smith 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 276 KB

In this paper, we study the sets where n is a positive integer. We show, in constrast to indications in some earlier work, that the sets R n are not completely determined by the Davenport constant of the class group of R. We offer some specific constructions for Dedekind domains with small class gr

The number of cycle lengths in graphs of

The number of cycle lengths in graphs of given minimum degree and girth

✍ P. Erdős; R.J. Faudree; C.C. Rousseau; R.H. Schelp 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 333 KB

This paper determines lower bounds on the number of different cycle lengths in a graph of given minimum degree k and girth g. The most general result gives a lower bound of ck ~.

On the distribution of cycle lengths in

On the distribution of cycle lengths in graphs

✍ A. Gyárfás; J. Komlós; E. Szemerédi 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 843 KB

The set of different cycle lengths of a graph G is denoted by C(G). We study how the distribution of C(G) depends on the minimum degree of G. We prove two results indicating that C(G) is dense in some sense. These results lead to the solution of a conjecture of Erdos and Hajnal stating that for suit

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