The Path Cover Number of k-Regular Graphs

The path cover number of a graph is the minimum number of vertex-disjoint paths required such that every vertex in the graph belongs to exactly one of the paths. This paper has three focuses: identifying strong bounds for the path cover number of connected 4-regular graphs, identifying an upper bound for the path cover number for any k-regular graph (with k ≥ 4), and introducing new variations of methods which offer the potential for improved bounds in the future. For connected 4-regular graphs, we construct a graph with 18 vertices and path cover number of 2, corresponding to a bound of n/9 , and show that for any N we can create a graph on n ≥ N vertices requiring at least n/12 paths. Additionally, for connected 4-regular graphs with n ≥ 8 vertices we prove an upper bound on path cover number of n/8 by a novel variation of the discharging method. The general notion of using discharging was introduced by Yu [13] on 2-connected 3-regular graphs, and used again by Feige and Fuchs [3] on 6-regular graphs. For k-regular graphs, we identify an upper bound of n/5 for k ≥ 4, using a simple generalization of an argument in Magnant and Martin [6], and introduce a new strategy which may lead to stronger bounds in the future.