Induced path factors of regular graphs. Issue 2 (18th December 2020)

• Record Type: Journal Article
• Authors: Akbari, Saieed; Horsley, Daniel; Wanless, Ian M.
• Is Part Of: Journal of graph theory. Volume 97:Issue 2(2021)
• Page Start: 260
• Page End: 280
• Publication Date: 2020-12-18
• Subjects: covering -- induced path -- path factor -- regular graph -- subcubic graph; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22654
• Languages: English
• ISSNs: 0364-9024

Abstract

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 → ∞ .