Long cycles in graphs with no subgraphs of minimal degree 3
type: Item
instance of: scholarly article
title: Long cycles in graphs with no subgraphs of minimal degree 3
zbMATH Open document ID: 0676.05051
DOI: 10.1016/0012-365X(89)90077-0
author: Béla Bollobás
author: Graham Brightwell
published in: Discrete Mathematics
publication date: 1989-01-01T00:00:00Z
review text: A graph G of order n is said to be degree k-critical if it has exactly \(n(k-1)-\binom{k}{2}+1\) edges and no proper subgraph of minimal degree k. Define \(f_ k(n)\) to be the minimum, over all degree k-critical graphs of order n, of the length of the longest cycle. \textit{P. Erdős, R. Faudree, A. Gyárfás} and \textit{R. H. Schelp} proved that \(\lfloor \log_ 2n\rfloor \leq f_ 3(n)\leq cn^{1/2}\) for some constant c. [Ars Comb. 25B, 195-201 (1988; Zbl 0657.05048)]. The authors prove that \(f_ 3(n)=4 \log_ 2n+O(\log_ 2\log_ 2n).\) Identical techniques can be extended to the case of general k.
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 4106889
zbMATH Keywords: degree k-critical graphs
zbMATH Keywords: longest cycle
MaRDI profile type: Publication
cites work: Q3804734
full work available at URL: 0012-365x(89)90077-0
OpenAlex ID: W1984046014
description: scientific article; zbMATH DE number 4106889