论文标题
树优化的有向图
Tree-optimized directed graphs
论文作者
论文摘要
对于$ \ mathbb {r} _ {\ ge 0} $的添加剂submonoid $ \ mathcal {m} $，$ \ mathcal {m} $ - 标记为导向的图形的重量是其所有边缘标签的总和，而内容是标签的产品。修复了$ \ Mathcal {m} $和有向的树$ e $后，我们证明了定向$ \ Mathcal {M} $的形状的一般结果，标记为$ n \ in \ MATHCAL {M} $最大化所有COPIES $ e \ e \ subset的内容的总和。 这专门用于恢复Hajac和Tobolski的结果，这是有向无环图中最大长度-K $路径的最大数量。它还适用于证明同一作者的猜想，以$ a^k $的最大条目总和，用于nilpotent $ \ mathbb {r} _ {\ ge 0} $ - 值的方形矩阵$ a $，其条目的条目又加$ n $。最后，我们采用相同的技术来获得带有$ n $边缘的定向图中的$ a $ and的最大恒星。
For an additive submonoid $\mathcal{M}$ of $\mathbb{R}_{\ge 0}$, the weight of an $\mathcal{M}$-labeled directed graph is the sum of all of its edge labels, while the content is the product of the labels. Having fixed $\mathcal{M}$ and a directed tree $E$, we prove a general result on the shape of directed $\mathcal{M}$-labeled graphs $Γ$ of weight $N\in \mathcal{M}$ maximizing the sum of the contents of all copies $E\subset Γ$. 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 $\mathbb{R}_{\ge 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.
