摘要
This paper studies the maximum number of edges of a Directed Acyclic Graph (DAG) with n vertices in terms of it's longest path l. We prove that in general this number is the Turan number t(n, l + 1), the maximum number of edges in a graph with n vertices without a clique of size l + 2. Furthermore, we find the maximum number of edges in a DAG which is either reduced, strongly reduced or extremely reduced and we relate this extremal result with the family of intersection graphs of families of boxes with transverse intersection.
- 出版日期2018