Binding number and minimum degree for fractional (k,m)-deleted graphs

Abstract

Let $G$ be a graph of order $n$, and let $k\geq1$ be an integer. Let $h: E(G)\rightarrow [0,1]$ be a function. If $\sum_{e\ni x}h(e)=k$ holds for any $x\in V(G)$, then we call $G[F_h]$ a fractional $k$-factor of $G$ with indicator function $h$ where $F_h=\{e\in E(G):h(e)>0\}$. A graph $G$ is called a fractional $(k,m)$-deleted graph if for every $e\in E(H)$, there exists a fractional $k$-factor $G[F_h]$ of $G$ with indicator function $h$ such that $h(e)=0$, where $H$ is any subgraph of $G$ with $m$ edges. The minimum degree of a vertex in $G$ is denoted by $\delta(G)$. For $X\subseteq V(G)$, $N_G(X)=\bigcup_{x\in X}N_G(x)$. The binding number of $G$ is defined by $bind(G)=\min\{\frac{|N_G(X)|}{|X|}:\emptyset\neq X\subset V(G), N_G(X)\neq V(G)\}$. In this paper, it is proved that if $n\geq4k-6+\frac{2m}{k-1}$, $bind(G)>\frac{(2k-1)(n-1)}{kn-2m}$ and $\delta(G)\geq1+\frac{(k-1)n+2m}{2k-1}$, then $G$ is a fractional $(k,m)$-deleted graph. Furthermore, it is shown that this result in this paper is best possible in some sense. DOI: 10.1017/S0004972711002784