{
  "id": "2201.11958",
  "version": "v1",
  "published": "2022-01-28T07:00:05.000Z",
  "updated": "2022-01-28T07:00:05.000Z",
  "title": "On maximum Wiener index of directed grids",
  "authors": [
    "Martin Knor",
    "Riste Skrekovski"
  ],
  "comment": "15 pages, 4 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "This paper is devoted to Wiener index of directed graphs, more precisely of directed grids. The grid $G_{m,n}$ is the Cartesian product $P_m\\Box P_n$ of paths on $m$ and $n$ vertices, and in a particular case when $m=2$, it is a called the ladder graph $L_n$. Kraner \\v{S}umenjak et al. proved that the maximum Wiener index of a digraph, which is obtained by orienting the edges of $L_n$, is obtained when all layers isomorphic to one factor are directed paths directed in the same way except one (corresponding to an endvertex of the other factor) which is a directed path directed in the opposite way. Then they conjectured that the natural generalization of this orientation to $G_{m,n}$ will attain the maximum Wiener index among all orientations of $G_{m,n}$. In this paper we disprove the conjecture by showing that a comb-like orientation of $G_{m,n}$ has significiantly bigger Wiener index.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-01-28T07:00:05.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "maximum wiener index",
      "directed grids",
      "orientation",
      "directed path",
      "significiantly bigger wiener index"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 15,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}