Tree-optimized labeled directed graphs

For an additive submonoid M of R_{≥ 0} , the weight of a finite M -labeled directed graph is the sum of all of its edge labels, while the content is the product of the labels. Having fixed M and a directed tree E, we prove a general result on the shape of finite, acyclic, M -labeled directed graphs Γ of weight N∈ M maximizing the sum of the contents of all copies E⊂ Γ . This specializes to recover a result of Hajac and the author’s on the maximal number of length-k paths in an acyclic directed graph with N edges. It also applies to prove a conjecture by the same authors on the maximal sum of entries of A^k for a nilpotent R_{≥ 0} -valued square matrix A whose entries add up to N. Finally, we apply the same techniques to obtain the maximal number of stars with α arms in a directed graph with N edges.