On the graph labellings arising from phylogenetics (Q386402)

Let \(G\) be a non-oriented graph. In this paper the authors study the so called phylogenetic semigroup \(\tau(G)\) of \(G\), which is a subsemigroup of the set of all labellings of edges of \(G\) by integers. This semigroup has a natural structure of graded semigroup with edge-wise addition and generalizes the semigroups studied in the Jukes-Cantor model and in phylogenetic toric varieties (see [\textit{W. Buczynska}, ``Phylogenetic toric varieties on graphs'', J. Algebraic Combin., 35(3), 421--460 (2012)]). The main result of this paper provides an upper bound for the degrees of the minimal generators of \(\tau(G)\). More precisely, the authors prove that any minimal generator of \(\tau(G)\) has degree at most \(g+1\), where \(g\) is the first Betti number of \(G\); i.e., \(g\) is the minimal number of cuts needed to make \(G\) acyclic. Moreover, the authors show that whenever \(g\) is even or \(g \in \{1,3\}\) this bound is sharp. More concretely, they show that the bound is attained for the \(g\)-caterpillar graph. The authors leave as an open question to see if this bound is sharp when \(g\) is odd and \(g \geq 5\). In this setting, they prove that the maximal degree of a generator of the phylogenetic semigroup of the \(g\)-caterpillar graph is \(g\).