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 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 and . 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 等数据库收录! |
|