{
  "id": "2306.09089",
  "version": "v1",
  "published": "2023-06-15T12:40:01.000Z",
  "updated": "2023-06-15T12:40:01.000Z",
  "title": "Mostar index and bounded maximum degree",
  "authors": [
    "Michael A. Henning",
    "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$. For a graph $G$ of order $n$ and maximum degree at most $\\Delta$, we show $Mo(G)\\leq \\frac{\\Delta}{2}n^2-(1-o(1))c_{\\Delta}n\\log(\\log(n)),$ where $c_{\\Delta}>0$ only depends on $\\Delta$ and the $o(1)$ term only depends on $n$. Furthermore, for integers $n_0$ and $\\Delta$ at least $3$, we show the existence of a $\\Delta$-regular graph of order $n$ at least $n_0$ with $Mo(G)\\geq \\frac{\\Delta}{2}n^2-c'_{\\Delta}n\\log(n),$ where $c'_{\\Delta}>0$ only depends on $\\Delta$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-06-15T12:40:01.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "bounded maximum degree",
      "mostar index",
      "regular graph",
      "smaller distance"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}