Cycles through specified vertices (Q684399): Difference between revisions

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.