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
    0 references
    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

    Identifiers