Induced path factors of regular graphs. Issue 2 (18th December 2020) - Akbari, Saieed; Horsley, Daniel; Wanless, Ian M.
Abstract: 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 ⩾ 3 . For each n, define ℳ n to be the maximum value of ρ ( G ) over all connected k ‐regular graphs G on n vertices. As n → ∞ with n k even, we show that c k = lim ( ℳ n / n ) exists. We prove that 5 / 18 ⩽ c 3 ⩽ 1 / 3 and 3 / 7 ⩽ c 4 ⩽ 1 / 2 and that c k = 1 2 − O ( k − 1 ) for k → ∞ .