...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Characterising (k,l)-leaf powers
【24h】

Characterising (k,l)-leaf powers

机译：表征（k，l）叶功率

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We say that, for k ≥ 2 and l > k, a tree T with distance function dT (x, y) is a (k,l)-leaf root of a finite simple graph G=(V, E) if V is the set of leaves of T , for all edges xy ∈ E, dT(x, y)≤ k, and for all non-edges xy ∈ E, dT (x, y)≥l. A graph is a (k,l)-leaf power if it has a (k,l)-leaf root. This new notion modifies the concept of k-leaf powers (which are, in our terminology, the (k, k+1)-leaf powers) introduced and studied by Nishimura, Ragde and Thilikos; k-leaf powers are motivated by the search for underlying phylogenetic trees. ecently, a lot of work has been done on k-leaf powers and roots as well as on their variants phylogenetic roots and Steiner roots. Many problems, however, remain open. We give the structural characterisations of (k, l)-leaf powers, for some k and l, which also imply an efficient recognition of these classes, and in this way we improve and extend a recent paper by Kennedy, Lin and Yan on strictly chordal graphs; one of our motivations for studying (k,l)-leaf powers is the fact that strictly chordal graphs are precisely the (4, 6)-leaf powers.
机译：我们说，对于k≥2且l> k，如果V为，则具有距离函数dT（x，y）的树T是有限简单图G =（V，E）的（k，l）叶根。 T的叶子集，对于所有边缘xy∈E，dT（x，y）≤k，对于所有非边缘xy∈E，dT（x，y）≥l。如果图具有（k，l）叶根，则它是（k，l）叶幂。这个新概念修改了由Nishimura，Ragde和Thilikos引入和研究的k叶幂的概念（在我们的术语中，是（k，k + 1）叶幂）。搜寻潜在的系统树会激发k叶的力量。有趣的是，已经对k叶的能力和根以及它们的变异系统发生根和Steiner根进行了大量工作。但是，许多问题仍然存在。对于某些k和l，我们给出了（k，l）-叶幂的结构特征，这也意味着对这些类别的有效识别，因此，我们对Kennedy，Lin和Yan的最新论文进行了严格的改进和扩展。和弦图我们研究（k，l）-叶幂的动机之一是严格的弦图恰好是（4，6）-叶幂的事实。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号