{
  "id": "2211.06682",
  "version": "v1",
  "published": "2022-11-12T15:01:16.000Z",
  "updated": "2022-11-12T15:01:16.000Z",
  "title": "Bounding the Mostar index",
  "authors": [
    "Štefko Miklavič",
    "Johannes Pardey",
    "Dieter Rautenbach",
    "Florian Werner"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Do\\v{s}li\\'{c} et al. defined the Mostar index of a graph $G$ as $Mo(G)=\\sum\\limits_{uv\\in E(G)}|n_G(u,v)-n_G(v,u)|$, where, for an edge $uv$ of $G$, the term $n_G(u,v)$ denotes the number of vertices of $G$ that have a smaller distance in $G$ to $u$ than to $v$. They conjectured that $Mo(G)\\leq 0.\\overline{148}n^3$ for every graph $G$ of order $n$. As a natural upper bound on the Mostar index, Geneson and Tsai implicitly consider the parameter $Mo^\\star(G)=\\sum\\limits_{uv\\in E(G)}\\big(n-\\min\\{ d_G(u),d_G(v)\\}\\big)$. For a graph $G$ of order $n$, they show that $Mo^\\star(G)\\leq \\frac{5}{24}(1+o(1))n^3$. We improve this bound to $Mo^\\star(G)\\leq \\left(\\frac{2}{\\sqrt{3}}-1\\right)n^3$, which is best possible up to terms of lower order. Furthermore, we show that $Mo^\\star(G)\\leq \\left(2\\left(\\frac{\\Delta}{n}\\right)^2+\\left(\\frac{\\Delta}{n}\\right)-2\\left(\\frac{\\Delta}{n}\\right)\\sqrt{\\left(\\frac{\\Delta}{n}\\right)^2+\\left(\\frac{\\Delta}{n}\\right)}\\right)n^3$ provided that $G$ has maximum degree $\\Delta$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-11-12T15:01:16.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "mostar index",
      "natural upper bound",
      "maximum degree",
      "smaller distance",
      "lower order"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}