INDEPENDENCE NUMBER, MINIMUM DEGREE AND PATH-FACTORS IN GRAPHS

A path-factor in a graph G is a spanning subgraph of G whose components are paths. Let d and k be two nonnegative integers with d >= 2. A P (>= d)-factor of a graph G is its spanning subgraph each of whose components is a path of order at least d. A graph G is called a P->= d-factor deleted graph if for any edge e of G, G admits a P->= d-factor excluding e. A graph G is called a (P->= d; k)-factor critical deleted graph if for any Q (sic) V (G) with vertical bar Q vertical bar = k, the graph G - Q is a P->= d-factor deleted graph. In other words, a graph G is called a (P->= d; k)-factor critical deleted graph if for any Q subset of V (G) with vertical bar Q vertical bar= k and any e is an element of E (G Q), the graph G Q e admits a P->= d-factor. In this paper, we prove that a (k + 2)-connected graph G is a (P->= 3; k)-factor critical deleted graph if G satisfies delta(G) > alpha(G)+ 2k + 2/2 . Furthermore, we show that the main result in this paper is best possible in some sense.