A note on extremal results on directed acyclic graphs
Abstract
This paper studies the maximum number of edges of a Directed Acyclic Graph (DAG) with n vertices in terms of it’s longest path ℓ. We prove that in general this number is the Turán number t(n, l + 1), the maximum number of edges in a graph with n vertices without a clique of size ℓ + 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.
Keywords
Directed graphs, Turán numbers, intersection graphs of families of boxes
DOI: https://doi.org/10.26493/1855-3974.1107.1c8
ISSN: 1855-3974
Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications