Tree-optimized labeled directed graphs

摘要

For an additive submonoidMof R->= 0, the weight of a finiteM-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 Gamma of weight N is an element of M maximizing the sum of the contents of all copies E subset of Gamma. 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 a arms in a directed graph with N edges.