Some New Results on $(g,f)$-Factorizations of Graphs

Abstract

Let $g$ and $f$ be integer-valued functions defined on $V(G)$ with $f(v)\ge g(v)\ge 1$ for all $v\in V(G)$. A graph $G$ is called a $(g,f)$-graph if $g(v)\le d_G(v)\le f(v)$ for each vertex $v\in V(G)$, and a $(g,f)$-factor of a graph $G$ is a spanning $(g,f)$-subgraph of $G$. A graph is $(g,f)$-factorable if its edges can be decomposed into $(g,f)$-factors.
The purpose of this paper is to prove the following three theorems: (i) If $m\ge 2$, every $((2mg+2m-2)t+(g+1)s,(2mf-2m+2)t+(f-1)s)$-graph $G$ is $(g,f)$-factorable. (ii) Let $g(x)$ be even and $m>2$. (1) If $m$ is even, and $G$ is a $((2mg+2)t+(g+1)s,(2mf-2m+4)t+(f-1)s)$-graph, then $G$ is $(g,f)$-factorable; (2) If $m$ is odd, and $G$ is a $((2mg+4)t+(g+1)s\$,\$(2mf-2m+2)t+(f-1)s)$-graph, then $G$ is $(g,f)$-factorable. (iii) Let $f(x)$ be even and $m>2$. (1) If $m$ is even, and $G$ is a $((2mg+2m-4)t+(g+1)s,(2mf-2)t+(f-1)s)$-graph, then $G$ is $(g,f)$-factorable;
(2) If $m$ is odd, and $G$ is a $((2mg+2m-2)t+(g+1)s$, $(2mf-4)t+(f-1)s)$-graph, then $G$ is $(g,f)$-factorable.
where $t$, $m$ are integers and $s$ is a nonnegative integer.