Acyclic digraphs and local hierarchy theory

The degree of a vertex of a digraph is the number of outgoing edges minus the number of incoming edges. Acyclic digraphs give a model for networks such as citation networks and organizational charts. Motivated by a “local hierarchy theory” developed for this model, we consider the set D̂(δ) of acyclic digraphs with a specified degree sequence δδ. We show that all digraphs in this set can be generated from any one such digraph using just one kind of basic transformation. In the case of degree sequences δδ that are minimal in the “Lorenz order”, we investigate the maximum number of edges in an acyclic digraph in D̂(δ) and show how to construct digraphs in D̂(δ) with many edges. Determining this maximum number of edges seems to be a very difficult problem.