Cycles through specified vertices
type: Item
instance of: scholarly article
title: Cycles through specified vertices
zbMATH Open document ID: 0780.05033
DOI: 10.1007/BF01303200
author: Béla Bollobás
author: Graham Brightwell
published in: Combinatorica
publication date: 1993-09-15T00:00:00Z
review text: The authors relax a minimum degree condition on a graph which guarantees long cycles and consider a set \(W\) of vertices with degree at least \(d\geq 1\), in a graph \(G\) with \(n\) vertices in total. Without imposing any further conditions on \(G\), it is shown that there is a cycle in \(G\) containing at least \(\bigl\lceil{| W|\over\lceil n/d\rceil- 1}\bigr\rceil\) vertices in \(W\). Extremal graphs are produced to show that the result is best possible.
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 411697
zbMATH Keywords: extremal graphs
zbMATH Keywords: long cycles
reviewed by: R. E. L. Aldred
MaRDI profile type: Publication
cites work: The longest cycle of a graph with a large minimal degree
cites work: Some Theorems on Abstract Graphs
cites work: The longest cycles in a graph G with minimum degree at least \(| G| /k\)
description: scientific article; zbMATH DE number 411697