Extremal number of arborescences
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910621194256384 |
|---|---|
| author | Bandekar, Aditya Csikvári, Péter Mascuch, Benjamin Tárkányi, Damján Telekes, Márton Tóthmérész, Lilla |
| author_facet | Bandekar, Aditya Csikvári, Péter Mascuch, Benjamin Tárkányi, Damján Telekes, Márton Tóthmérész, Lilla |
| contents | In this paper we study the following extremal graph theoretic problem: Given an undirected Eulerian graph $G$, which Eulerian orientation minimizes or maximizes the number of arborescences? We solve the minimization for the complete graph $K_n$, the complete bipartite graph $K_{n,m}$, and for the so-called double graphs, where there are even number of edges between any pair of vertices.
In fact, for $K_n$ we prove the following stronger statement. If $T$ is a tournament on $n$ vertices with out-degree sequence $d_1^+,\dots ,d^+_n$, then $$\mathrm{allarb}(T)\geq \frac{1}{n}\left(\prod_{k=1}^n(d^+_k+1)+\prod_{k=1}^nd^+_k\right),$$ where $\mathrm{allarb}(T)$ is the total number of arborescences. Equality holds if and only if $T$ is a locally transitive tournament.
We also give an upper bound for the number of arborescences of an Eulerian orientation for an arbitrary graph $G$. This upper bound can be achieved on $K_n$ for infinitely many $n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_17893 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Extremal number of arborescences Bandekar, Aditya Csikvári, Péter Mascuch, Benjamin Tárkányi, Damján Telekes, Márton Tóthmérész, Lilla Combinatorics 05B20, 05C50, 05A20, 05C35 In this paper we study the following extremal graph theoretic problem: Given an undirected Eulerian graph $G$, which Eulerian orientation minimizes or maximizes the number of arborescences? We solve the minimization for the complete graph $K_n$, the complete bipartite graph $K_{n,m}$, and for the so-called double graphs, where there are even number of edges between any pair of vertices. In fact, for $K_n$ we prove the following stronger statement. If $T$ is a tournament on $n$ vertices with out-degree sequence $d_1^+,\dots ,d^+_n$, then $$\mathrm{allarb}(T)\geq \frac{1}{n}\left(\prod_{k=1}^n(d^+_k+1)+\prod_{k=1}^nd^+_k\right),$$ where $\mathrm{allarb}(T)$ is the total number of arborescences. Equality holds if and only if $T$ is a locally transitive tournament. We also give an upper bound for the number of arborescences of an Eulerian orientation for an arbitrary graph $G$. This upper bound can be achieved on $K_n$ for infinitely many $n$. |
| title | Extremal number of arborescences |
| topic | Combinatorics 05B20, 05C50, 05A20, 05C35 |
| url | https://arxiv.org/abs/2409.17893 |