Convex sets in acyclic digraphs

DOI10.1007/S11083-009-9109-9MaRDI QIDQ1016095zbMATH OpenOpenAlexFDO

Authors Stefanie Gerke, G. Gutin, Paul Balister

Publication date 4 May 2009

Published in Order (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0712.2678

zbMATH Keywords

acyclic digraphsconvex sets

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

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 $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(ncdotco(D))$ ($Theta(ncdotcc(D))$) where $n$ is the order of $D$. In this paper we exhibit a family of connected acyclic digraphs with $su{m}_{Cinsco(D)}|C|=o(ncdotco(D))$ and $su{m}_{Cinscc(D)}|C|=o(ncdotcc(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.

Recommendations

• Algorithms for generating convex sets in acyclic digraphs
• On the number of connected convex subgraphs of a connected acyclic digraph
• scientific article; zbMATH DE number 4085678
• scientific article; zbMATH DE number 3865341
• An Algorithm for Finding Input-Output Constrained Convex Sets in an Acyclic Digraph

Cites work

• Algorithms for generating convex sets in acyclic digraphs
• An Algorithm for Finding Input-Output Constrained Convex Sets in an Acyclic Digraph
• scientific article; zbMATH DE number 1498519 (Why is no real title available?)
• On the number of connected convex subgraphs of a connected acyclic digraph

Cited in

(7)

• On the number of connected convex subgraphs of a connected acyclic digraph
• Algorithms for generating convex sets in acyclic digraphs
• Convex sets under some graph operations
• scientific article; zbMATH DE number 4085678 (Why is no real title available?)
• An algorithm for finding input-output constrained convex sets in an acyclic digraph
• An Algorithm for Finding Input-Output Constrained Convex Sets in an Acyclic Digraph
• A new notion of convexity in digraphs with an application to Bayesian networks

This page was built for publication: Convex sets in acyclic digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1016095)