A note on extremal results on directed acyclic graphs

Authors

  • Álvaro Martínez-Pérez
  • Luis Montejano
  • Deborah Oliveros Instituto de Matemáticas

DOI:

https://doi.org/10.26493/1855-3974.1107.1c8

Keywords:

Directed graphs, Turán numbers, intersection graphs of families of boxes

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.

Author Biography

Deborah Oliveros, Instituto de Matemáticas

Professor

Published

2018-02-06

Issue

Section

Articles