A note on the path cover number of regular graphs
Colton Magnant, Daniel Michael Martin · 2009
Let G be a simple graph of order n. The path cover number μ(G )i s defined to be the minimum number of vertex disjoint paths required to cover the vertices of G. Ore proved that in general μ(G) ≤ max{1 ,n − σ2(G)}. We conjecture that if G is k-regular, then μ(G) ≤ n k+1 and we prove this for k ≤ 5.