{
  "id": "2209.08946",
  "version": "v1",
  "published": "2022-09-19T11:54:33.000Z",
  "updated": "2022-09-19T11:54:33.000Z",
  "title": "On the Wiener Index of Orientations of Graphs",
  "authors": [
    "Peter Dankelmann"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "The Wiener index of a strong digraph $D$ is defined as the sum of the distances between all ordered pairs of vertices. This definition has been extended to digraphs that are not necessarily strong by defining the distance from a vertex $a$ to a vertex $b$ as $0$ if there is no path from $a$ to $b$ in $D$. Knor, \\u{S}krekovski and Tepeh [Some remarks on Wiener index of oriented graphs. Appl.\\ Math.\\ Comput.\\ {\\bf 273}] considered orientations of graphs with maximum Wiener index. The authors conjectured that for a given tree $T$, an orientation $D$ of $T$ of maximum Wiener index always contains a vertex $v$ such that for every vertex $u$, there is either a $(u,v)$-path or a $(v,u)$-path in $D$. In this paper we disprove the conjecture. We also show that the problem of finding an orientation of maximum Wiener index of a given graph is NP-complete, thus answering a question by Knor, \\u{S}krekovski and Tepeh [Orientations of graphs with maximum Wiener index. Discrete Appl.\\ Math.\\ 211]. We briefly discuss the corresponding problem of finding an orientation of minimum Wiener index of a given graph, and show that the special case of deciding if a given graph on $m$ edges has an orientation of Wiener index $m$ can be solved in time quadratic in $n$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-09-19T11:54:33.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C12",
      "05C20",
      "05C85"
    ],
    "keywords": [
      "maximum wiener index",
      "orientation",
      "minimum wiener index",
      "strong digraph",
      "special case"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}