Component factors and binding number conditions in graphs

Abstract

Let $ G $ be a graph. For a set $ \mathcal{H} $ of connected graphs, an $ \mathcal{H} $-factor of a graph $ G $ is a spanning subgraph $ H $ of $ G $ such that every component of $ H $ is isomorphic to a member of $ \mathcal{H} $. A graph $ G $ is called an $ (\mathcal{H}, m) $-factor deleted graph if for every $ E'\subseteq E(G) $ with $ |E'| = m $, $ G-E' $ admits an $ \mathcal{H} $-factor. A graph $ G $ is called an $ (\mathcal{H}, n) $-factor critical graph if for every $ N\subseteq V(G) $ with $ |N| = n $, $ G-N $ admits an $ \mathcal{H} $-factor. Let $ m $, $ n $ and $ k $ be three nonnegative integers with $ k\geq2 $, and write $ \mathcal{F} = \{P_2, C_3, P_5, \mathcal{T}(3)\} $ and $ \mathcal{H} = \{K_{1, 1}, K_{1, 2}, \cdots, K_{1, k}, \mathcal{T}(2k+1)\} $, where $ \mathcal{T}(3) $ and $ \mathcal{T}(2k+1) $ are two special families of trees. In this article, we verify that (i) a $ (2m+1) $-connected graph $ G $ is an $ (\mathcal{F}, m) $-factor deleted graph if its binding number $ bind(G)\geq\frac{4m+2}{2m+3} $; (ii) an $ (n+2) $-connected graph $ G $ is an $ (\mathcal{F}, n) $-factor critical graph if its binding number $ bind(G)\geq\frac{2+n}{3} $; (iii) a $ (2m+1) $-connected graph $ G $ is an $ (\mathcal{H}, m) $-factor deleted graph if its binding number $ bind(G)\geq\frac{2}{2k-1} $; (iv) an $ (n+2) $-connected graph $ G $ is an $ (\mathcal{H}, n) $-factor critical graph if its binding number $ bind(G)\geq\frac{2+n}{2k+1} $.

Keywords

• graph
• binding number
• h-factor
• (h，m)-factor deleted graph
• (h，n)-factor critical graph