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

2022/05/22 by Hasanvand, Morteza
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2205.10874

Abstract

Let G be a graph and let f be a positive integer-valued function on V(G) satisfying 2m≤ f≤ b, where b and m are two positive integers with b≥ 4m². In this paper, we show that if G is b²-tough and |V(G)|≥ b², then it has an m-tree-connected factor H such that for each vertex v, d_H(v)∈ \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)∈ \f(v), f(v)+k\. As an application, we prove that every 64b(b-a)²-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≤ a< b < (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).

Related

• The existence of tree-connected \g,f\-factors in edge-connected graphs and tough graphs
• Toughness and existence of 2-factors
• Factors and connected factors in tough graphs with high isolated\n toughness
• Existence of 2-Factors in Tough Graphs without Forbidden Subgraphs
• The existence of m-tree-connected (g,f+f'-m)-factors using (g,f)-factors and m-tree-connected (m,f')-factors