Induced path factors of regular graphs

An induced path factor of a graph G is a set of induced paths in G with the property that every vertex of G is in exactly one of the paths. The induced path number ρ(G) of G is the minimum number of paths in an induced path factor of G. We show that if G is a connected cubic graph on n>6 vertices, then ρ(G)≤(n-1)/3.

Fix an integer k\ge3. For each n, define M_n to be the maximum value of ρ(G) over all connected k-regular graphs G on n vertices. As n\rightarrow\infty with nk even, we show that c_k=\lim(M_n/n) exists. We prove that 5/18≤c₃≤1/3 and 3/7≤c₄≤1/2 and that c_k=\frac12-O(k^-1) for k→∞.