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,\dots ,s_k,t_1,t_2,\dots ,t_k$ be any $2k$ distinct vertices of $G$. If there exist $k$ disjoint paths $P_1,P_2,\dots ,P_k$ such that $P_i$ is an $s_i–t_i$ path for $1\le i\le k$, we call $G$ $k$-linked. K. Kawarabayashi et al. showed that if $n\ge 4k–1$ ($k\ge 2$) with ${\sigma }_2(G)\ge n+2k–3$, then $G$ is $k$-linked. Li et al. showed that if $G$ is a graph of order $n\ge 232k$ with ${\sigma }_2^{\ast }(G)\ge 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\ge 111k+9$ with ${\sigma }_2^{\ast }(G)\ge n+2k–3$, then $G$ is $k$-linked. Thus, we improve the order bound to $111k+9$, and when $n\ge 111k+9$, it implies the result of $K$. Kawarabayashi $etal$.