Tight Toughness Bounds for Fractional (k, n)-Critical Graphs with Large n

Abstract

A graph G is called a fractional (k, n)-critical graph if G − V ′ admits a fractional k-factor for any V ′ ⊆ V (G) with |V′| = n. The main result in this paper states the following facts: 1) G is fractional (2, n)-critical if t(G) > and n ≥ 3; 2) G is fractional (2, 2)-critical if t(G) > ; 3) G is fractional (k, n)-critical if t(G) > with n ≥ k ≥ 3. Furthermore, the sharpness of the given toughness bounds are illustrated by counterexamples.