• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Order >Convex Sets in Acyclic Digraphs
【24h】

Convex Sets in Acyclic Digraphs

机译：无环有向图的凸集

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

摘要

A non-empty set X of vertices of an acyclic digraph is called connected if the underlying undirected graph induced by X is connected and it is called convex if no two vertices of X are connected by a directed path in which some vertices are not in X. The set of convex sets (connected convex sets) of an acyclic digraph D is denoted by CO(D) (CC(D)) and its size by co(D) (cc(D)). Gutin et al. (2008) conjectured that the sum of the sizes of all convex sets (connected convex sets) in D equals Θ(n · co(D)) (Θ(n · cc(D))) where n is the order of D. In this paper we exhibit a family of connected acyclic digraphs with ∑_(c∈co(D))) |C| = o(n·co(D)) and ∑_(c∈co(D))) |C| = o(n·co(D)). We also show that the number of connected convex sets of order k in any connected acyclic digraph of order n is at least n - k + 1. This is a strengthening of a theorem of Gutin and Yeo.
机译：如果连接了由X诱导的基础无向图，则将无环有向图的顶点的非空集合X称为连接；如果没有X的两个顶点通过有向路径连接的情况（其中某些顶点不在X中），则将其称为凸形。非循环有向图D的凸集的集合（连通凸集）用CO（D）（CC（D））表示，其大小用co（D）（cc（D））表示。 Gutin等。 （2008）推测D中所有凸集（连通凸集）的大小之和等于Θ（n·co（D））（Θ（n·cc（D））），其中n是D的阶数。在本文中，我们展示了一个具有∑_（c∈co（D）））| C |的连通无环图族。 = o（n·co（D））和∑_（c∈co（D）））| C | ＝ o（n·co（D））。我们还表明，在阶数为n的任何连接的无环有向图中，阶数为k的连接凸集的数量至少为n-k +1。这是对Gutin和Yeo定理的加强。

著录项

  • 来源
    《Order》 |2009年第1期|95-100|共6页
  • 作者

    Paul Balister; Stcfanic Gerke; Gregory Gutin;

  • 作者单位

    Department of Mathematical Sciences, University of Memphis, Memphis, TN 38152-3240, USA;

    Department of Computer Science, Royal Holloway, University of London, Egham, TW20 0EX, UK;

    Department of Computer Science, Royal Holloway, University of London,Egham, TW20 0EX, UK;

  • 收录信息 美国《科学引文索引》(SCI);
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

    acyclic diagraphs; convex sets;

    机译：无环图凸集;

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号