Polynomial invariants for cactuses

van Iersel, Leo, Moulton, Vincent ORCID: https://orcid.org/0000-0001-9371-6435 and Murakami, Yukihiro (2023) Polynomial invariants for cactuses. Information Processing Letters, 182. ISSN 0020-0190

Preview

PDF (1-s2.0-S0020019023000376-main) - Published Version Available under License Creative Commons Attribution. Download (374kB) | Preview

Abstract

Graph invariants are a useful tool in graph theory. Not only do they encode useful information about the graphs to which they are associated, but complete invariants can be used to distinguish between non-isomorphic graphs. Polynomial invariants for graphs such as the well-known Tutte polynomial have been studied for several years, and recently there has been interest to also define such invariants for phylogenetic networks, a special type of graph that arises in the area of evolutionary biology. Recently Liu gave a complete invariant for (phylogenetic) trees. However, the polynomial invariants defined thus far for phylogenetic networks that are not trees require vertex labels and either contain a large number of variables, or they have exponentially many terms in the number of reticulations. This can make it difficult to compute these polynomials and to use them to analyse unlabelled networks. In this paper, we shall show how to circumvent some of these difficulties for rooted cactuses and cactuses. As well as being important in other areas such as operations research, rooted cactuses contain some common classes of phylogenetic networks such phylogenetic trees and level-1 networks. More specifically, we define a polynomial F that is a complete invariant for the class of rooted cactuses without vertices of indegree 1 and outdegree 1 that has 5 variables, and a polynomial Q that is a complete invariant for the class of rooted cactuses that has 6 variables whose degree can be bounded linearly in terms of the size of the rooted cactus. We also explain how to extend the Q polynomial to define a complete invariant for leaf-labelled rooted cactuses as well as (unrooted) cactuses.

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:	14 Apr 2023 09:30
Last Modified:	20 Jun 2023 14:50
URI:	https://ueaeprints.uea.ac.uk/id/eprint/91765
DOI:	10.1016/j.ipl.2023.106394

Downloads

Actions (login required)

View Item