TOUGHNESS, ISOLATED TOUGHNESS AND PATH FACTORS IN GRAPHS

Abstract

Abstract A graph G is called a $(P_{\geq n},k)$ -factor-critical covered graph if for any $Q\subseteq V(G)$ with $|Q|=k$ and any $e\in E(G-Q)$ , $G-Q$ has a $P_{\geq n}$ -factor covering e . We demonstrate that (i) a $(k+1)$ -connected graph G with at least $k+3$ vertices is a $(P_{\geq 3},k)$ -factor-critical covered graph if its toughness $t(G)>{(2+k)}/{3}$ ; (ii) a $(k+2)$ -connected graph G is a $(P_{\geq 3},k)$ -factor-critical covered graph if its isolated toughness $I(G)>{(5+k)}/{3}$ . Furthermore, we show that the conditions on $t(G)$ and $I(G)$ are sharp.

Topics & Concepts