Tree-optimized labeled directed graphs

Abstract: For an additive submonoid

m a t h c a l M

of

m a t h b b R_{g e 0}

, the weight of an

m a t h c a l 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 a t h c a l M

and a directed tree

E

, we prove a general result on the shape of directed

m a t h c a l M

-labeled graphs

G a m m a

of weight

N i n m a t h c a l M

maximizing the sum of the contents of all copies

E s u b s e t G a m m a

. This specializes to recover a result of Hajac and Tobolski on the maximal number of length-

k

paths in a directed acyclic graph. It also applies to prove a conjecture by the same authors on the maximal sum of entries of

A^{k}

for a nilpotent

m a t h b b R_{g e 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.

Recommendations

Cites work

This page was built for publication: Tree-optimized labeled directed graphs