A note on extremal results on directed acyclic graphs

作者:Martinez Perez Alvaro*; Montejano Luis; Oliveros Deborah
来源:Ars Mathematica Contemporanea, 2018, 14(2): 445-454.
DOI:10.26493/1855-3974.1107.1c8

摘要

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