Counting vertices and cubes in median graphs of circular split systems
Counting vertices and cubes in median graphs of circular split systems
复制标题
DOI：
10.1016/j.ejc.2007.02.003
复制
发表时间：
2008-02
期刊：
影响因子：
--
通讯作者：
Y. Choe;K. Huber;J. Koolen;Y. Kwon;V. Moulton
中科院分区：
文献类型：
--
作者：
Y. Choe;K. Huber;J. Koolen;Y. Kwon;V. Moulton
中值图是树和超立方体的自然推广，它们与分配格和图收缩密切相关。在过去的十年中，它们已经成为生物界越来越感兴趣的，在那里，除其他外，它们被应用于种群内进化关系的研究。中位数图复杂性的两个简单度量是顶点数和最大诱导子立方体数。这些数字在生物学应用中可能很有用，它们也具有纯粹的数学意义。然而，它们通常很难计算。在这里，我们提出了一些特殊的家庭的中位数图，它是可能的，找到这些数字的公式和递归。
Median graphs are a natural generalisation of trees and hypercubes that are closely related to distributive lattices and graph retracts. In the past decade, they have become of increasing interest to the biological community, where, amongst other things, they are applied to the study of evolutionary relationships within populations. Two simple measures of complexity for a median graph are the number of vertices and the number of maximal induced subcubes. These numbers can be useful in biological applications, and they are also of purely mathematical interest. However, they can be hard to compute in general. Here we present some special families of median graphs where it is possible to find formulae and recursions for these numbers.