Degree conditions for path-factors in graphs
Ping Zhang · RAIRO - Operations Research · 2024
A spanning subgraph H of a graph G is called a path-factor if every component of H is a path. Wang and Zhang [RAIRO:RO 57 (2023) 2231–2237] conjectured that a connected graph G with δ(G) ≥ 5 contains a {P2, P5}-factor if δ(G)≥3α(G)−14, where δ(G) and α(G) denote the minimum degree and independence number of G, respectively. We show that the conjecture is true except G ≅ X ∨ 7K3, where X is a spanning subgraph of K3. Furthermore, we give two degree conditions for the existence of {P2, P5}-factors, one of which is a stronger version of Wang’s another conjecture. We also show the degree conditions are best possible.