On the graph labellings arising from phylogenetics (Q386402): Difference between revisions
From MaRDI portal
Latest revision as of 04:09, 7 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the graph labellings arising from phylogenetics |
scientific article |
Statements
On the graph labellings arising from phylogenetics (English)
0 references
9 December 2013
0 references
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\).
0 references
graph labellings
0 references
phylogenetic semigroup
0 references
semigroup generators
0 references
lattice cone
0 references
Hilbert basis
0 references
conformal block algebras
0 references
Cavender-Farris-Neyman model
0 references
2-state Jukes-Cantor model
0 references
0 references