摘要
Let ∊ (0, 1] be a real number and let n be a sufficiently large integer. We prove that every n-vertex cn-regular graph G contains a collection of [1/c] paths whose union covers all but at most o(n) vertices of G. The constant [1/c] is best possible when 1/c/∉ ℕ and off by 1 otherwise. Moreover, if in addition G is bipartite, then the number of paths can be reduced to [1/(2c)], which is best possible.
源语言 | 英语 |
---|---|
文章编号 | #P2.12 |
期刊 | Electronic Journal of Combinatorics |
卷 | 25 |
期 | 2 |
DOI | |
出版状态 | 已出版 - 27 4月 2018 |
已对外发布 | 是 |
指纹
探究 'On vertex-disjoint paths in regular graphs' 的科研主题。它们共同构成独一无二的指纹。引用此
Han, J. (2018). On vertex-disjoint paths in regular graphs. Electronic Journal of Combinatorics, 25(2), 文章 #P2.12. https://doi.org/10.37236/7109