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 ?



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

Well, this is embarrassing. I was able to answer the first half of my question after a quick discussion with a student.

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$.

To build an example, I can start with a DAG that has k nodes and a "maximal number of edges". Then I recursively add a vertex that has k edges towards the graph obtained at the previous iteration.

I am still interested by good references for solving the problem using random directed graphs with a bounded average out-degree.

To give some background to why I was asking this question. I am interested by the worst-case complexity of the following problem. I start with a directed graph and recursively remove all the leaves (nodes with out-degree zero) until I am blocked. When I remove a vertex, I also remove all the edges to and from this vertex. I know that the graph is a DAG if and only if I can remove all its vertices.

In the context of my problem, the cost of each iteration is equal to the number of vertices in the graph (at that particular time), plus the number of transitions.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.