On vertex-disjoint paths in regular graphs (Q1753085)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On vertex-disjoint paths in regular graphs
scientific article

    Statements

    On vertex-disjoint paths in regular graphs (English)
    0 references
    0 references
    25 May 2018
    0 references
    Summary: Let \(c\in (0, 1]\) be a real number and let \(n\) be a sufficiently large integer. We prove that every \(n\)-vertex \(c n\)-regular graph \(G\) contains a collection of \(\lfloor 1/c \rfloor\) paths whose union covers all but at most \(o(n)\) vertices of \(G\). The constant \(\lfloor 1/c \rfloor\) is best possible when \(1/c\notin \mathbb{N}\) and off by \(1\) otherwise. Moreover, if in addition \(G\) is bipartite, then the number of paths can be reduced to \(\lfloor 1/(2c) \rfloor\), which is best possible.
    0 references
    regular graphs
    0 references
    paths
    0 references

    Identifiers