The simple graph threshold number $\sigma (r,s,a,t)$

Abstract

For $d\ge 1$, $s\ge 0$ a $(d,d+s)$-{\em graph} is a graph whose degrees all lie in the interval $\{d,d+1,\dots ,d+s\}$. For $r\ge 1$, $a\ge 0$, an $(r,r+a)$-{\em factor} of a graph $G$ is a spanning $(r,r+a)$-subgraph of $G$. An $(r,r+a)$-{\em factorization} of a graph $G$ is a decomposition of $G$ into edge-disjoint $(r,r+a)$-factors. A graph is $(r,r+a)$-{\em factorable} if it has an $(r,r+a)$-factorization. Let $\sigma (r,s,a,t)$ be the least integer such that, if $d\ge \sigma (r,s,a,t)$, then every $(d,d+s)$-simple graph $G$ is $(r,r+a)$-factorable with $x$ factors for at least $t$ different values of $x$. In this paper we evaluate $\sigma (r,s,a,t)$ for all values of $r,s,a$ and $t$. We also show that if $a\ge 2$ and $r\ge 1$, then, when $r$ is even and $a$ is odd, every $(d,d+s)$-simple graph $G$ has an $(r,r+a)$-factorization with $x$ factors if and only if $$\frac{d+s}{r+a}<x\le \frac{d}{r},$$ and we prove similar statements for other parities of $r$ and $a$.

38 pages, 4 figures