{
  "id": "2011.13970",
  "version": "v1",
  "published": "2020-11-27T19:18:43.000Z",
  "updated": "2020-11-27T19:18:43.000Z",
  "title": "Wiener index in graphs with given minimum degree and maximum degree",
  "authors": [
    "Peter Dankelmann",
    "Alex Alochukwu"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $G$ be a connected graph of order $n$.The Wiener index $W(G)$ of $G$ is the sum of the distances between all unordered pairs of vertices of $G$. In this paper we show that the well-known upper bound $\\big( \\frac{n}{\\delta+1}+2\\big) {n \\choose 2}$ on the Wiener index of a graph of order $n$ and minimum degree $\\delta$ [M. Kouider, P. Winkler, Mean distance and minimum degree. J. Graph Theory 25 no. 1 (1997)] can be improved significantly if the graph contains also a vertex of large degree. Specifically, we give the asymptotically sharp bound $W(G) \\leq {n-\\Delta+\\delta \\choose 2} \\big( \\frac{n+2\\Delta}{\\delta+1}+4 \\big)$ on the Wiener index of a graph $G$ of order $n$, minimum degree $\\delta$ and maximum degree $\\Delta$. We prove a similar result for triangle-free graphs, and we determine a bound on the Wiener index of $C_4$-free graphs of given order, minimum and maximum degree and show that it is, in some sense, best possible.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-11-27T19:18:43.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C12",
      "92E10"
    ],
    "keywords": [
      "wiener index",
      "minimum degree",
      "maximum degree",
      "well-known upper bound",
      "mean distance"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}