Path-factor critical covered graphs and path-factor uniform graphs
Jie Wu
Abstract
A path-factor in a graph G is a spanning subgraph F of G such that every component of F is a path. Let d and n be two nonnegative integers with d ≥ 2. A P ≥ d -factor of G is its spanning subgraph each of whose components is a path with at least d vertices. A graph G is called a P ≥ d -factor covered graph if for any e ∈ E ( G ), G admits a P ≥ d -factor containing e . A graph G is called a ( P ≥ d , n )-factor critical covered graph if for any N ⊆ V ( G ) with | N | = n , the graph G − N is a P ≥ d -factor covered graph. A graph G is called a P ≥ d -factor uniform graph if for any e ∈ E ( G ), the graph G − e is a P ≥ d -factor covered graph. In this paper, we verify the following two results: (i) An ( n + 1)-connected graph G of order at least n + 3 is a ( P ≥3 , n )-factor critical covered graph if G satisfies δ ( G ) > (α(G)+2 n +3)/2; (ii) Every regular graph G with degree r ≥ 2 is a P ≥3 -factor uniform graph.