Edge-decompositions of O(m)-edge-connected graphs into isomorphic copies of a fixed tree of size m

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

paper · doi:10.48550/arxiv.2205.10871

Abstract

In this paper, we show that every O(m)-edge-connected simple graph G of size divisible by m with minimum degree at least 2^O(m) has an edge-decomposition into isomorphic copies of any given tree T of size m. Moreover, the minimum degree condition can be dropped for graphs G with girth greater than the diameter of T. These results improve two results due to Bensmail, Harutyunyan, Le, Merker, and Thomassé (2017) and Merker (2017) who gave a factorial upper bound on the necessary edge-connectivity.

Related

• Decomposing highly edge-connected graphs into homomorphic copies of a\n fixed tree
• Edge-decomposition of graphs into copies of a tree with four edges
• Edge-connectivity keeping trees in k-edge-connected graphs
• Edge-decomposing graphs into coprime forests
• Non-branching tree-decompositions