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, 33 (3). ISSN 1077-8926

Preview	PDF (foldings) - Accepted Version Available under License Creative Commons Attribution No Derivatives. Download (635kB) | Preview
Preview	PDF (14805-PDF file-63574-1-10-20260914) - Published Version Available under License Creative Commons Attribution No Derivatives. Download (623kB) | Preview

Abstract

In 1989 Erdős and Székely 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 multi-labeled 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
Related URLs:	https://www.scopus.com/pages/publication...
Depositing User:	LivePure Connector
Date Deposited:	17 Sep 2026 09:29
Last Modified:	07 Oct 2026 07:47
URI:	https://ueaeprints.uea.ac.uk/id/eprint/104573
DOI:	10.37236/14805

Downloads

Actions (login required)

View Item