论文标题
仙人掌多项式不变
Polynomial invariants for cactuses
论文作者
论文摘要
图形不变是图理论中的有用工具。它们不仅编码有关与之关联的图形的有用信息，而且可以使用完整的不变性来区分非同构图。已经研究了诸如众所周知的Tutte多项式诸如图形的多项式不变式，最近也有兴趣为系统发育网络定义此类不变性，这是在进化生物学领域产生的一种特殊类型的图。最近，刘给了（系统发育）树完全不变。但是，迄今为止针对非树木的系统发育网络定义的多项式不变式需要顶点标签，并且要么包含大量变量，要么在网状数量中具有指数式的术语。这可能使计算这些多项式并使用它们来分析未标记网络变得困难。在本文中，我们将展示如何解决其中一些困难的根源仙人掌和仙人掌。在其他领域（例如操作研究）中，根源的仙人掌还包含一些常见的系统发育网络类别，例如系统发育树和Level-1网络。更具体地说，我们定义了一个多项式$ f $，它对于没有indegree 1和具有5个变量的超级1和超级1的顶点的根顶仙人掌是一个完全不变的，而多项式$ q $，是一个完全不变的，对于具有6个变量\ vince的limeal lineal lineal lineal carte n and carteed n of and carteed的caccactuse cactise cacked and and and of and of and andeal nike的cact cacked and carte n of and and ande n size neceed n of and carte neceed n earked neceed。我们还解释了如何扩展$ q $多项式，以定义叶片标记的根仙人掌以及（未根除的）仙人掌的完整不变。
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 \vince{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.
