Toughness and the existence of tree-connected $\{f,f+k\}$-factors

Abstract

Let $G$ be a graph and let $f$ be a positive integer-valued function on $V(G)$ satisfying $2m\le f\le b$, where $b$ and $m$ are two positive integers with $b\ge 4m^2$. In this paper, we show that if $G$ is $b^2$-tough and $|V(G)|\ge b^2$, then it has an $m$-tree-connected factor $H$ such that for each vertex $v$, $$d_H(v)\in \{f(v),f(v)+1\}.$$ Next, we generalize this result by giving sufficient conditions for a tough graph to have a tree-connected factors $H$ such that for each vertex $v$, $d_H(v)\in \{f(v),f(v)+k\}$. As an application, we prove that every $64b(b-a{)}^2$-tough graph $G$ of order at least $b+1$ with $ab|V(G)|$ even admits a connected factor whose degrees lie in the set $\{a,b\}$, where $a$ and $b$ are two integers with $2\le a<b<\frac{6}{5}a$. Moreover, we prove that every $16$-tough graph $G$ of order at least three admits a $2$-connected factor whose degrees lie in the set $\{2,3\}$, provided that $G$ has a $2$-factor with girth at least five. This result confirms a weaker version of a long-standing conjecture due to Chvátal (1973).

This paper is an improved version of a removed part of the paper arXiv:1702.06203. arXiv admin note: substantial text overlap with arXiv:2205.05044