Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2511.18952 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914168771182592 |
|---|---|
| author | Gao, Hui |
| author_facet | Gao, Hui |
| contents | The celebrated Nash-Williams and Tutte's theorem states that a graph $G=(V, E)$ contains $k$ edge disjoint spanning trees if and only if $ν_{f}(G) \geq k$, where $$ν_{f}(G):=\min_{|\mathcal{\mathcal{P}}|>1, \text{$\mathcal{P}$ is a partition of $V(G)$}}\frac{|E( \mathcal{P})|}{|\mathcal{P}|-1}.$$ Inspired by the NDT theorem as structural explanations for the fractional part of Nash-Williams' forest decomposition theorem, Fang and Yang extended Nash-Williams and Tutte's theorem and proved that if $ν_{f}(G) > k+ \frac{d-1}{d}$, then $G$ contains $k$ edge disjoint spanning trees and another forest $F$ with $ |E(F)|> \frac{d-1}{d} (|V(G)|-1)|$, and if $F$ is not a spanning tree, then $F$ has a component with at least $d$ edges. In this paper, we give a digraphic version of their result; however, the mixed graphic version remains open. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_18952 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Packing spanning arborescences with extra large one Gao, Hui Combinatorics The celebrated Nash-Williams and Tutte's theorem states that a graph $G=(V, E)$ contains $k$ edge disjoint spanning trees if and only if $ν_{f}(G) \geq k$, where $$ν_{f}(G):=\min_{|\mathcal{\mathcal{P}}|>1, \text{$\mathcal{P}$ is a partition of $V(G)$}}\frac{|E( \mathcal{P})|}{|\mathcal{P}|-1}.$$ Inspired by the NDT theorem as structural explanations for the fractional part of Nash-Williams' forest decomposition theorem, Fang and Yang extended Nash-Williams and Tutte's theorem and proved that if $ν_{f}(G) > k+ \frac{d-1}{d}$, then $G$ contains $k$ edge disjoint spanning trees and another forest $F$ with $ |E(F)|> \frac{d-1}{d} (|V(G)|-1)|$, and if $F$ is not a spanning tree, then $F$ has a component with at least $d$ edges. In this paper, we give a digraphic version of their result; however, the mixed graphic version remains open. |
| title | Packing spanning arborescences with extra large one |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2511.18952 |