Extremal Number of Arborescences

Aditya Bandekar¹ ; Péter Csikvári² ; Benjamin Mascuch³ ; Damján Tárkányi⁴ ; Márton Telekes⁵ ; Lilla Tóthmérész⁶

¹University of Toronto
²HUN-REN Alfréd Rényi Institute of Mathematics and ELTE Eötvös Loránd University
³Tufts University
⁴ELTE Eötvös Loránd University
⁵Budapest University of Technology and Economics
⁶Eötvös Loránd University

The electronic journal of combinatorics, Tome 32 (2025) no. 4

Résumé

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 ${\rm 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$.

Détail

DOI : 10.37236/13517