# Maximal number of edges in a DAG when we bound the degree of the nodes

Hello,

Does anyone know how to build an acyclic directed graph with N nodes such that both: (1) the degree of the nodes is bounded (say less than k); and (2) the number of edges in the graph is maximal ?

I know that the problem is trivial if I lift condition (1); the maximal number of edges in this case is N(N-1)/2.

Could you point me to the right theory to apply if I am interested by graphs where the average degree is less than k, or where all but a fixed percentage of nodes has degree less than k ?

Sincerely,

Silvano

• Should this DAG be a subgraph of some given graph? Oct 11 '11 at 11:45

If I assume that $N \gg k$, the maximal number of edges in my graph is in $\Theta(k.N)$, as expected. The most precise answer, assuming that $N > k$ is $k.(N-k) + k.(k-1) / 2$.