An Improved Fan-Type Degree Condition for \(k\)-Linked Graphs

Abstract

Let \(G\) be a graph of order at least \(2k\) and \(s_1, s_2, \ldots, s_k, t_1, t_2, \ldots, t_k\) be any \(2k\) distinct vertices of \(G\). If there exist \(k\) disjoint paths \(P_1, P_2, \ldots, P_k\) such that \(P_i\) is an \(s_i – t_i\) path for \(1 \leq i \leq k\), we call \(G\) \(k\)-linked. K. Kawarabayashi et al. showed that if \(n \geq 4k – 1\) (\(k \geq 2\)) with \(\sigma_2(G) \geq n + 2k – 3\), then \(G\) is \(k\)-linked. Li et al. showed that if \(G\) is a graph of order \(n \geq 232k\) with \(\sigma_2^*(G) \geq 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 bound of \(n\) in the result of Li et al. We show that if \(G\) is a graph of order \(n \geq 111k + 9\) with \(\sigma_2^*(G) \geq n + 2k – 3\), then \(G\) is \(k\)-linked. Thus, we improve the order bound to \(111k + 9\), and when \(n \geq 111k + 9\), it implies the result of \(K\). Kawarabayashi \(et al\).