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.
@article{1107,
title = {A note on extremal results on directed acyclic graphs},
journal = {ARS MATHEMATICA CONTEMPORANEA},
volume = {15},
year = {2018},
doi = {10.26493/1855-3974.1107.1c8},
language = {EN},
url = {http://dml.mathdoc.fr/item/1107}
}
Martínez-Pérez, Álvaro; Montejano, Luis; Oliveros, Deborah. A note on extremal results on directed acyclic graphs. ARS MATHEMATICA CONTEMPORANEA, Tome 15 (2018) . doi : 10.26493/1855-3974.1107.1c8. http://gdmltest.u-ga.fr/item/1107/