Fractional factors, component factors and isolated vertex conditions in graphs (Q2278109)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Fractional factors, component factors and isolated vertex conditions in graphs |
scientific article |
Statements
Fractional factors, component factors and isolated vertex conditions in graphs (English)
0 references
9 December 2019
0 references
Summary: For a graph \(G\), a 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 \(\mathrm{iso}(G-S) \le (k+\frac{1}{2})|S|\) is equivalent to the existence of fractional \([1,k+ \frac{1}{2}]\)-factors, where \(\mathrm{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 \(\mathrm{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 \(\mathrm{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.
0 references
fractional \([a, b]\)-factor
0 references