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