Two Sufficient Conditions for Graphs to Admit Path Factors

Let 𝒜 be a set of connected graphs. Then a spanning subgraph A of G is called an 𝒜-factor if each component of A is isomorphic to some member of 𝒜. Especially, when every graph in 𝒜 is a path, A is a path factor. For a positive integer d ≥ 2, we write 𝒫 ≥ d = 𝒫 i | i ≥ d. Then a 𝒫 ≥ d -factor means a path factor in which every component admits at least d vertices. A graph G is called a (𝒫 ≥ d, m) -factor deleted graph if G – E′ admits a 𝒫 ≥ d -factor for any E′ ⊆ E (G) with | E′| = m. A graph G is called a (𝒫 ≥ d, k) -factor critical graph if G – Q has a 𝒫 ≥ d -factor for any Q ⊆ V (G) with | Q| = k. In this paper, we present two degree conditions for graphs to be (𝒫 ≥3, m) -factor deleted graphs and (𝒫 ≥3, k) -factor critical graphs. Furthermore, we show that the two results are best possible in some sense.