科研之友
微信
新浪微博
Facebook
分享链接
摘要
Let G be a graph of order at least 2k and s(1), s(2), ... , s(k) , t(1), t(2), ... , t(k) be any 2k distinct vertices of G, if there exist k disjoint paths P-1, P-2, ..., P-k such that P-i is an s(i) - t(i) path for 1 <= i <= k, we call that G is k-linked. K. Kawarabayashi et al. showed that if n >= 4k-1(k >= 2) with sigma(2)(G) >= n + 2k-3, then G is k-linked. Li et al. showed that if G is a graph of order n >= 232k with sigma(*)(2)(G) >= n + 2k-3, then G is k-linked. For sufficiently large n, it implied the result of K. Kawarabayashi et al. The main purpose of this paper is to lower the down bound of n in the result of Li et al.. We show that if G is a graph of order n >= 111k + 9 with sigma(*)(2) (G) >= n+2k-3, then G is k-linked. Thus, we improve the order bound to 111k +9, and when n >= 111k + 9, it implies the result of K. Kawarabayashi et al.
