Maximal Line Digraphs

Abstract

A line digraph $L(G)=(A,E)$ is the digraph constructed from the digraph $G=(V,A)$ such that there is an arc $(a,b)$ in $L(G)$ if the terminal node of $a$ in $G$ is the initial node of $b$. The maximum number of arcs in a line digraph with $m$ nodes is $(m/2{)}^2+(m/2)$ if $m$ is even, and $((m-1)/2{)}^2+m-1$ otherwise. For $m\ge 7$, there is only one line digraph with as many arcs if $m$ is even, and if $m$ is odd, there are two line digraphs, each being the transpose of the other.