Path Extendability and Degree Sum in Graphs

Abstract

In this paper, we study the relations between degree sum and extending paths in graphs. The following result is proved. Let $G$ be a graph of order $n$, if $d(u)+d(v)\ge n+k$ for each pair of nonadjacent vertices $u,v$ in $V(G)$, then every path $P$ of $G$ with $\frac{n}{k+2}\le 2<n$ is extendable. The bound $\frac{n}{k+2}+2$ is sharp.