Augmenting a hypergraph to have a matroid-based $(f,g)$-bounded $(α,β)$-limited packing of rooted hypertrees
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909415573028864 |
|---|---|
| author | Hoppenot, Pierre Szigeti, Zoltán |
| author_facet | Hoppenot, Pierre Szigeti, Zoltán |
| contents | The aim of this paper is to further develop the theory of packing trees in a graph. We first prove the classic result of Nash-Williams \cite{NW} and Tutte \cite{Tu} on packing spanning trees by adapting Lovász' proof \cite{Lov} of the seminal result of Edmonds \cite{Egy} on packing spanning arborescences in a digraph. Our main result on graphs extends the theorem of Katoh and Tanigawa \cite{KT} on matroid-based packing of rooted trees by characterizing the existence of such a packing satisfying the following further conditions: for every vertex $v$, there are a lower bound $f(v)$ and an upper bound $g(v)$ on the number of trees rooted at $v$ and there are a lower bound $α$ and an upper bound $β$ on the total number of roots. We also answer the hypergraphic version of the problem. Furthermore, we are able to solve the augmentation version of the latter problem, where the goal is to add a minimum number of edges to have such a packing. The methods developed in this paper to solve these problems may have other applications in the future. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_03363 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Augmenting a hypergraph to have a matroid-based $(f,g)$-bounded $(α,β)$-limited packing of rooted hypertrees Hoppenot, Pierre Szigeti, Zoltán Combinatorics Discrete Mathematics The aim of this paper is to further develop the theory of packing trees in a graph. We first prove the classic result of Nash-Williams \cite{NW} and Tutte \cite{Tu} on packing spanning trees by adapting Lovász' proof \cite{Lov} of the seminal result of Edmonds \cite{Egy} on packing spanning arborescences in a digraph. Our main result on graphs extends the theorem of Katoh and Tanigawa \cite{KT} on matroid-based packing of rooted trees by characterizing the existence of such a packing satisfying the following further conditions: for every vertex $v$, there are a lower bound $f(v)$ and an upper bound $g(v)$ on the number of trees rooted at $v$ and there are a lower bound $α$ and an upper bound $β$ on the total number of roots. We also answer the hypergraphic version of the problem. Furthermore, we are able to solve the augmentation version of the latter problem, where the goal is to add a minimum number of edges to have such a packing. The methods developed in this paper to solve these problems may have other applications in the future. |
| title | Augmenting a hypergraph to have a matroid-based $(f,g)$-bounded $(α,β)$-limited packing of rooted hypertrees |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2412.03363 |