The maximal spectral radius of a digraph with (m+1)^2-s edges
From MaRDI portal
Publication:4450692
Abstract: It is known that the spectral radius of a digraph with k edges is le sqrt{k}, and that this inequality is strict except when k is a perfect square. For k=m^2 + ell, ell 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 ell/2
floor vertices by pairs of directed edges (this is for odd ell, for even ell 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
eq 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
floor pairs of directed edges that connect to the last vertex (if s is even, remove an extra edge connecting to the last vertex).
Recommendations
Cited in
(4)
This page was built for publication: The maximal spectral radius of a digraph with (m+1)^2-s edges
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4450692)
