Iterated line digraphs are asymptotically dense

Abstract

We show that the line digraph technique, when iterated, provides dense digraphs, that is, with asymptotically large order for a given diameter (or with small diameter for a given order). This is a well-known result for regular digraphs. In this note we prove that this is also true for non-regular digraphs.

This research is supported by projects MINECO MTM2014-60127-P, and 2014SGR1147 of the Catalan Government. This research has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922.