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) \geq n+k\) for each pair of nonadjacent vertices \(u,v\) in \(V(G)\), then every path \(P\) of \(G\) with \(\frac{n}{k+2} \leq 2 < n\) is extendable. The bound \(\frac{n}{k+2}+2\) is sharp.