Qinglin Yu

For a graph $G = (V, E)$, a {\em fractional $[a, b]$-factor} is a real valued function $h:E(G)\to [0,1]$ that satisfies $a \le ~ \sum_{e\in E_G(v)} h(e) ~ \le b$ for all $ v\in V(G)$, where $a$ and $b$ are real numbers and $E_G(v)$ denotes the set of edges incident with $v$. In this paper, we prove that the condition $\mathit{iso}(G-S) \le (k+\frac{1}{2})|S|$ is equivalent to the existence of fractional $[1,k+ \frac{1}{2}]$-factors, where ${\mathit{iso}}(G-S)$ denotes the number of isolated vertices in $G-S$. Using fractional factors as a tool, we construct component factors under the given isolated conditions. Namely, (i) a graph $G$ has a $\{P_2,C_3,P_5, \mathcal{T}(3)\}$-factor if and only if $\mathit{iso}(G-S) \le \frac{3}{2}|S|$ for all $S\subset V(G)$; (ii) a graph $G$ has a $\{K_{1,1}, K_{1,2}, \ldots,$ $K_{1,k}, \mathcal{T}(2k+1)\}$-factor ($k\ge 2$) if and only if $\mathit{iso}(G-S) \le (k+\frac{1}{2})|S|$ for all $S\subset V(G)$, where $\mathcal{T}(3)$ and $\mathcal{T}(2k+1)$ are two special families of trees.

A connected graph $G$ with at least $2m + 2n + 2$ vertices which contains a perfect matching is $E(m, n)$-{\it extendable}, if for any two sets of disjoint independent edges $M$ and $N$ with $|M| = m$ and $|N|= n$, there is a perfect matching $F$ in $G$ such that $M\subseteq F$ and $N\cap F=\emptyset$. Similarly, a connected graph with at least $n+2k+2$ vertices is called $(n,k)$-{\it extendable} if for any vertex set $S$ of size $n$ and any matching $M$ of size $k$ of $G-S$, $G-S-V(M)$ contains a perfect matching. Let $\varepsilon$ be a small positive constant, $b(G)$ and $t(G)$ be the binding number and toughness of a graph $G$. The two main theorems of this paper are: for every graph $G$ with sufficiently large order, 1) if $b(G)\geq 4/3+\varepsilon$, then $G$ is $E(m,n)$-extendable and also $(n,k)$-extendable; 2) if $t(G)\geq 1+\varepsilon$ and $G$ has a high connectivity, then $G$ is $E(m,n)$-extendable and also $(n,k)$-extendable. It is worth to point out that the binding number and toughness conditions for the existence of the general matching extension properties are almost same as that for the existence of perfect matchings.

Let $G$ be a graph, and $H\colon V(G)\to 2^\mathbb{N}$ a set function associated with $G$. A spanning subgraph $F$ of $G$ is called an $H$-factor if the degree of any vertex $v$ in $F$ belongs to the set $H(v)$. This paper contains two results on the existence of $H$-factors in regular graphs. First, we construct an $r$-regular graph without some given $H^*$-factor. In particular, this gives a negative answer to a problem recently posed by Akbari and Kano. Second, by using Lov\'asz's characterization theorem on the existence of $(g, f)$-factors, we find a sharp condition for the existence of general $H$-factors in $\{r, r+1\}$-graphs, in terms of the maximum and minimum of $H$. The result reduces to Thomassen's theorem for the case that $H(v)$ consists of the same two consecutive integers for all vertices $v$, and to Tutte's theorem if the graph is regular in addition.