Advertisement
Published in:
01-05-2023
Tree-optimized labeled directed graphs
Published in: Journal of Combinatorial Optimization | Issue 4/2023
Log inActivate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
For an additive submonoid \({\mathcal {M}}\) of \(\mathbb {R}_{\ge 0}\), the weight of a finite \({\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 finite, acyclic, \({\mathcal {M}}\)-labeled directed graphs \(\Gamma \) of weight \(N\in {\mathcal {M}}\) maximizing the sum of the contents of all copies \(E\subset \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 \(\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 \(\alpha \) arms in a directed graph with N edges.