{
  "id": "2201.00186",
  "version": "v2",
  "published": "2022-01-01T13:09:30.000Z",
  "updated": "2022-04-18T17:50:40.000Z",
  "title": "Maximum size of digraphs of given radius",
  "authors": [
    "Stijn Cambie"
  ],
  "comment": "22 pages, 15 figures, this paper is an extended version of a second part of arXiv:1903.01358, mainly clarifying the content of section 5, where the bipartite cases are considered as well. Furthermore a foreword and table with figures of the extremal (di)graphs has been added for clarification",
  "categories": [
    "math.CO"
  ],
  "abstract": "In $1967$, Vizing determined the maximum size of a graph with given order and radius. In $1973$, Fridman answered the same question for digraphs with given order and outradius. We investigate that question when restricting to biconnected digraphs. Biconnected digraphs are the digraphs with a finite total distance and hence the interesting ones, as we want to note a connection between minimizing the total distance and maximizing the size under the same constraints. We characterize the extremal digraphs maximizing the size among all biconnected digraphs of order $n$ and outradius $3$, as well as when the order is sufficiently large compared to the outradius. As such, we solve a problem of Dankelmann asymptotically. We also consider these questions for bipartite digraphs and solve a second problem of Dankelmann partially.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2022-04-18T17:50:40.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C20",
      "05C35"
    ],
    "keywords": [
      "maximum size",
      "biconnected digraphs",
      "finite total distance",
      "bipartite digraphs",
      "second problem"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 22,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}