On cycle lengths in graphs of moderate degree
type: Item
instance of: scholarly article
title: On cycle lengths in graphs of moderate degree
zbMATH Open document ID: 0796.05057
DOI: 10.1016/0012-365X(94)90143-0
author: H. Bencherif Ait-Djafer
published in: Discrete Mathematics
publication date: 1994-09-15T00:00:00Z
review text: It is shown that for all \(\varepsilon>0\), an integer \(N(\varepsilon)\) exists such that if \(G\) is any graph of order \(n \geq N (\varepsilon)\) with minimum degree \(\delta \geq 32 \sqrt n\), \(G\) contains a cycle of length \(2l\) for each \(l\), \(2 \leq l \leq \delta / (16 + \varepsilon)\). This is a consequence of the following result: If \(l \geq 2\), any bipartite \(G\) of order \(n\) with \(\delta \geq 8l n^{1/l}\) has a cycle of length \(2l\). This last statement holds because otherwise, if we denote by \(V_ i\) the set of vertices of distance \(i\) from an arbitrarily chosen vertex, we have \(| V_ i |/ | V_{i-1} | \geq n^{1/l}\). The inequality yields \(| V |>n\), a contradiction.
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 562646
zbMATH Keywords: pancyclic graphs
zbMATH Keywords: degree conditions
zbMATH Keywords: cycle
reviewed by: Norman F. Quimpo
MaRDI profile type: Publication
cites work: Hamiltonian pancyclic graphs
cites work: Large cycles in graphs
cites work: Pancyclic graphs. I
cites work: Q4041607
cites work: Q4087221
cites work: Cycles of even length in graphs
cites work: Some Theorems on Abstract Graphs
cites work: On the structure of linear graphs
cites work: On some extremal problems in graph theory
cites work: Q3944634
cites work: Pancyclic graphs and a conjecture of Bondy and Chvatal
cites work: Bipartite graphs with cycles of all even lengths
cites work: Sufficient Conditions for Circuits in Graphs†
cites work: Q3680866
description: scientific article; zbMATH DE number 562646