首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Convex Sets in Acyclic Digraphs
Authors:Paul Balister  Stefanie Gerke  Gregory Gutin
Institution:(1) Department of Mathematical Sciences, University of Memphis, Memphis, TN 38152-3240, USA;(2) Department of Computer Science, Royal Holloway, University of London, Egham, TW20 0EX, UK
Abstract: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 $\mathcal{CO}(D) \ (\mathcal{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 $\sum_{C\in \mathcal{CO}(D)}|C| = o(n\cdot \mathrm{co}(D))$ and $\sum_{C\in \mathcal{CC}(D)}|C| = o(n\cdot \mathrm{cc}(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.
Keywords:Acyclic diagraphs  Convex sets
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号