Abstract :

Given and edge weighted undirected graph $G=(V,E)$ with $|V|=n$, and a function $fV mapsto mathbb{N}$, we consider the problem of finding a connected $f$-factor in $G$. In particular, for each constant $cge 2$, we consider the case when $f(v)ge frac{n}{c}$, for all $v$ in $V$. We characterize the set of graphs that have a connected $f$-factor for $f(v) ge frac{n}{3}$, for every $v$ in $V$, and this gives a polynomial time algorithm for the decision version of the problem. Extending the techniques, we solve the minimization version.