solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看105次
On vertex-disjoint paths in regular graphs. (arXiv:1706.06945v1 [math.CO])
来源于:arXiv
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. 查看全文>>