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

DOI10.13001/1081-3810.1105zbMATH Open1047.05029arXivmath/0210365OpenAlexW2962928228MaRDI QIDQ4450692FDOQ4450692

Authors: J. E. Snellman 

Publication date: 15 February 2004

Published in: The Electronic Journal of Linear Algebra (Search for Journal in Brave)

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).

Full work available at URL: https://arxiv.org/abs/math/0210365

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• On the spectral radius of simple digraphs with prescribed number of arcs
• Improved upper and lower bounds for the spectral radius of digraphs
• Improved bounds for the spectral radius of digraphs
• Spectral radius of strongly connected digraphs
• scientific article; zbMATH DE number 1877024

zbMATH Keywords

digraphmaximal spectral radius

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38)

Cited In (4)

• Title not available (Why is that?)
• Variable neighborhood search for extremal graphs. 16. Some conjectures related to the largest eigenvalue of a graph
• Spectra of digraphs
• On the spectral radius of simple digraphs with prescribed number of arcs

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)