2002/10/31 by Jan Snellman
Mathematics · #math.CO #math.RA #msc:05C50 #msc:05C20 #msc:05C38
published as Electronic Journal of Linear Algebra, vol 10 (2003), pp 179-189 · 11 pages, 9 eps figures. To be presented at the conference FPSAC03. Submitted to Electronic Journal of Linear Algebra. Keywords: Spectral radius, digraphs, 0-1 matrices, Perron-Frobenius theorem, number of walks
arxiv created 2003/03/11 · arxiv updated 2009/11/30
It is known that the spectral radius of a digraph with k edges is ≤ √(k), and that this inequality is strict except when k is a perfect square. For k=m2 + ℓ, ℓ fixed, m large, Friedland showed that the optimal digraph is obtained from the complete digraph on m vertices by adding one extra vertex, and a corresponding loop, and then connecting it to the first \lfloor ℓ/2\rfloor vertices by pairs of directed edges (this is for odd ℓ, for even ℓ we add one extra edge to the new vertex). Using a combinatorial reciprocity theorem by Gessel, and a classification by Backelin on the digraphs on s edges having a maximal number of walks of length two, we obtain the following result: for fixed 0< s ≠ 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 \lfloor s/2 \rfloor pairs of directed edges that connect to the last vertex (if s is even, remove an extra edge connecting to the last vertex).