Edge-decompositions of $O(m)$-edge-connected graphs into isomorphic copies of a fixed tree of size $m$
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929479769653248 |
|---|---|
| author | Hasanvand, Morteza |
| author_facet | Hasanvand, Morteza |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2205_10871 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Edge-decompositions of $O(m)$-edge-connected graphs into isomorphic copies of a fixed tree of size $m$ Hasanvand, Morteza Combinatorics 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. |
| title | Edge-decompositions of $O(m)$-edge-connected graphs into isomorphic copies of a fixed tree of size $m$ |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2205.10871 |