TIGHT TOUGHNESS CONDITION FOR FRACTIONAL (g, f, n)-CRITICAL GRAPHS

A graph G is called a fractional (g,f,n)-critical graph if any n vertices are removed from G, then the resulting graph admits a fractional (g,f)-factor. In this paper, we determine the new toughness condition for fractional (g,f,n)-critical graphs. It is proved that G is fractional (g,f,n)-critical if t(G) � b 2 −1+bn a . This bound is sharp in some sense. Furthermore, the best toughness condition for fractional (a, b,n)-critical graphs is given. All graphs considered in this paper are finite, loopless, and without multiple edges. The notation and terminology used but undefined in this paper can be found in (2). Let G be a graph with the vertex set V (G) and the edge set E(G). For a vertex x ∈ V (G), we use dG(x) and NG(x) to denote the degree and the neighborhood of x in G, respectively. Let �(G) denote the minimum degree of G. For any S ⊆ V (G), the subgraph of G induced by S is denoted by G(S). Suppose that g and f are two integer-valued functions on V (G) such that 0 ≤ g(x) ≤ f(x) for all x ∈ V (G). A spanning subgraph F of G is called a (g,f)-factor if g(x) ≤ dF(x) ≤ f(x) for each x ∈ V (G). A fractional (g,f)- factor is a function h that assigns to each edge of a graph G a number in (0,1) so that for each vertex x we have g(x) ≤ P e∈E(x) h(e) ≤ f(x). If g(x) = a, f(x) = b for all x ∈ V (G), then a fractional (g,f)-factor is a fractional (a,b)- factor. Moreover, if g(x) = f(x) = k (k ≥ 1 is an integer throughout this paper, and we will not reiterate it again) for all x ∈ V (G), then a fractional (g,f)-factor is just a fractional k-factor.