Covering the vertices of a graph by vertex-disjoint paths
Shahbaz Noorvash · Pacific Journal of Mathematics · 1975
Define the path-covering number μ(G) of a finite graph G to be the minimum number of vertex-disjoint paths required to cover the vertices of G Let g(n,k) be the minimum integer so that every graph, G, with n vertices and at least g(n,k) edges has μ(G)^=k.A relationship between μ(G) and the degree sequence for a graph G is found; this is used to show that λ 2 (n -k)(n -k -1)+ 1 ^ g(n,k) ^{{n -\){n -k -1) + 1