𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

✍ Scribed by P. Erdős; R.J. Faudree; C.C. Rousseau; R.H. Schelp

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
333 KB
Volume
200
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

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

📜 SIMILAR VOLUMES

Cycle lengths in graphs with large minim
Cycle lengths in graphs with large minimum degree
✍ V. Nikiforov; R. H. Schelp 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 114 KB 👁 1 views

## Abstract Our main result is the following theorem. Let __k__ ≥ 2 be an integer, __G__ be a graph of sufficiently large order __n__, and __δ__(__G__) ≥ __n__/__k__. Then: __G__ contains a cycle of length __t__ for every even integer __t__ ∈ [4, __δ__(__G__) + 1]. If __G__ is nonbipartite then

The number of cutvertices in graphs with
The number of cutvertices in graphs with given minimum degree
✍ L.H. Clark; R.C. Entringer 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 453 KB

The maximum number of cutvertices in a connected graph of order n having minimum degree at least 6 is determined for 6 > 5.

The number of cut-vertices in a graph of
The number of cut-vertices in a graph of given minimum degree
✍ Michael O. Albertson; David M. Berman 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 228 KB

Albertson, M.O. and D.M. Berman, The number of cut-vertices in a graph of given minimum degree, Discrete Mathematics 89 (1991) 97-100. A graph with n vertices and minimum degree k 2 2 can contain no more than (2k -2)n/(kz -2) cut-vertices. This bound is asymptotically tight. \* Research supported in

On the independent domination number of
On the independent domination number of graphs with given minimum degree
✍ N.I. Glebov; A.V. Kostochka 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 175 KB

We prove a new upper bound on the independent domination number of graphs in terms of the number of vertices and the minimum degree. This bound is slightly better than that of Haviland (1991) and settles the case 6 = 2 of the corresponding conjecture by Favaron (1988). @ 1998 Elsevier Science B.V. A

On cycle lengths in graphs of moderate d
On cycle lengths in graphs of moderate degree
✍ H. Bencherif Ait-Djafer 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 447 KB

We show that for all positive E, an integer N(E) exists such that if G is any graph of order n>N(s) with minimum degree 63324 then G contains a cycle of length 21 for each integer 1, 2<1<~/(16+s). Bondy [4] and Woodall [15] have obtained sufficient conditions for a graph to contain cycles of each le