ELA, Volume 10, pp. 179-189, July 2003, abstract.

The maximal spectral radius of a digraph with (m+1)^2-s edges

Jan Snellman

It is known that the  spectral radius of a digraph with k edges 
is at most the square root of k, and that this inequality is strict 
except when k is a perfect square. For k=m^2+l, l fixed, m large,
Friedland showed that the optimal digraph is obtained from the 
complete digraph on m vertices by adding one extra vertex, a 
corresponding loop, and then connecting it to the first l/2 (or 
greatest integer less than l/2) vertices by pairs of directed edges 
(for even l an extra edge is added to the new vertex). 

Using a combinatorial reciprocity theorem, and a classification by 
Backelin on the digraphs on s edges having a maximal number of walks 
of length two, the following result is obtained: for fixed positive s
(s not equal to 4), k=(m+1)^2-s, m large, the maximal spectral radius 
of a digraph with k edges is obtained by the digraph which is constructed 
from the complete digraph on m+1 vertices by removing the loop at the 
last vertex together with s/2 (or greatest integer less than s/2) pairs 
of directed edges that connect to the last vertex (if s is even, remove 
an extra edge connecting the last vertex).