Cycles through specified vertices (Q684399)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Cycles through specified vertices |
scientific article |
Statements
Cycles through specified vertices (English)
0 references
15 September 1993
0 references
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.
0 references
extremal graphs
0 references
long cycles
0 references