Convex sets in acyclic digraphs
| dc.creator | Balister, P. | |
| dc.creator | Gerke, S. | |
| dc.creator | Gutin, G. | |
| dc.date | 2007-12-17 | |
| dc.date.accessioned | 2026-07-07T08:49:39Z | |
| dc.date.available | 2026-07-07T08:49:39Z | |
| dc.description | 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 $Θ(n \cdot \co(D))$ ($Θ(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. | |
| dc.identifier | https://arxiv.org/abs/0712.2678 | |
| dc.identifier | http://arxiv.org/abs/0712.2678 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/144375 | |
| dc.subject | Discrete Mathematics | |
| dc.title | Convex sets in acyclic digraphs | |
| dc.type | text |