{
  "id": "math/0210365",
  "version": "v4",
  "published": "2002-10-23T12:06:00.000Z",
  "updated": "2003-03-11T12:13:23.000Z",
  "title": "The maximal spectral radius of a digraph with (m+1)^2 - s edges",
  "authors": [
    "Jan Snellman"
  ],
  "comment": "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",
  "journal": "Electronic Journal of Linear Algebra, vol 10 (2003), pp 179-189",
  "categories": [
    "math.CO",
    "math.RA"
  ],
  "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\\rfloor 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 \\neq 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).",
  "revisions": [
    {
      "version": "v4",
      "updated": "2003-03-11T12:13:23.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C50",
      "05C20",
      "05C38"
    ],
    "keywords": [
      "maximal spectral radius",
      "extra edge",
      "complete digraph",
      "combinatorial reciprocity theorem",
      "directed edges"
    ],
    "tags": [
      "conference paper",
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 11,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2002math.....10365S"
    }
  }
}