Fractional Factors, Component Factors and Isolated Vertex Conditions in Graphs

Abstract

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 $iso(G-S)\le (k+\frac{1}{2})|S|$ is equivalent to the existence of fractional $[1,k+\frac{1}{2}]$-factors, where $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 $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},\dots ,$ $K_{1,k},\mathcal{T}(2k+1)\}$-factor ($k\ge 2$) if and only if $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.

Cited by in corpus (1)

• Fractional factors and component factors in graphs with isolated toughness smaller than 1