Convex sets in acyclic digraphs

Details Convex sets in acyclic digraphs Convex sets in acyclic digraphs

2007-12-17

arxiv.org/abs/0712.2678v1

Computer Science

Discrete Mathematics

Scientific paper

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 $\sco(D)$ ($\scc(D)$) and its size by $\co(D)$ ($\cc(D)$). Gutin, Johnstone, Reddington, Scott, Soleimanfallah, and Yeo (Proc. ACiD'07) conjectured that the sum of the sizes of all (connected) convex sets in $D$ equals $\Theta(n \cdot \co(D))$ ($\Theta(n \cdot \cc(D))$) where $n$ is the order of $D$. In this paper we exhibit a family of connected acyclic digraphs with $\sum_{C\in \sco(D)}|C| = o(n\cdot \co(D))$ and $\sum_{C\in \scc(D)}|C| = o(n\cdot \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 by Gutin and Yeo.

Affiliated with

Also associated with

No associations

Rating

Convex sets in acyclic digraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Convex sets in acyclic digraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Convex sets in acyclic digraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-116072