2024/09/26 by Bandekar, Aditya, Csikvári, Péter, Mascuch, Benjamin +3
#05A20 #05B20 #05C35 #05C50 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2409.17893
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 Kn, the complete bipartite graph Kn,m, and for the so-called double graphs, where there are even number of edges between any pair of vertices. In fact, for Kn we prove the following stronger statement. If T is a tournament on n vertices with out-degree sequence d1+,… ,d+n, then allarb(T)≥ (1)/(n)(∏k=1n(d+k+1)+∏k=1nd+k), where 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 Kn for infinitely many n.