Labeling and folding multi-labeled trees

Moulton, Vincent ORCID: https://orcid.org/0000-0001-9371-6435 and Spillner, Andreas (2026) Labeling and folding multi-labeled trees. Electronic Journal of Combinatorics. ISSN 1077-8926 (In Press)

PDF (foldings) - Accepted Version Restricted to Repository staff only until 31 December 2099. Available under License Creative Commons Attribution No Derivatives. Request a copy

Abstract

In 1989 Erd˝os and Sz´ekely showed that there is a bijection between (i) the set of rooted trees with n + 1 vertices whose leaves are bijectively labeled with the elements of [ℓ] = {1, 2, . . . , ℓ} for some ℓ ⩽ n, and (ii) the set of partitions of [n] = {1, 2, . . . , n}. They established this via a labeling algorithm based on the anti-lexicographic ordering of non-empty subsets of [n] which extends the labeling of the leaves of a given tree to a labeling of all of the vertices of that tree. In this paper, we generalize their approach by developing a labeling algorithm for multilabeled trees, that is, rooted trees whose leaves are labeled by positive integers but in which distinct leaves may have the same label. In particular, we show that certain orderings of the set of all finite, non-empty multisets of positive integers can be used to characterize partitions of a multiset that arise from labelings of multi-labeled trees. As an application, we show that the recently introduced class of labelable phylogenetic networks is precisely the class of phylogenetic networks that are stable relative to the so-called folding process on multi-labeled trees. We also give a bijection between the labelable phylogenetic networks with leaf-set [n] and certain partitions of multisets.

Item Type:	Article
Faculty \ School:	Faculty of Science > School of Computing Sciences
UEA Research Groups:	Faculty of Science > Research Groups > Norwich Epidemiology Centre Faculty of Medicine and Health Sciences > Research Groups > Norwich Epidemiology Centre Faculty of Science > Research Groups > Computational Biology
Depositing User:	LivePure Connector
Date Deposited:	17 Sep 2026 09:29
Last Modified:	17 Sep 2026 09:29
URI:	https://ueaeprints.uea.ac.uk/id/eprint/104573
DOI:	issn:1077-8926

Actions (login required)

View Item