Wiener index in graphs with given minimum degree and maximum degree

Alex Alochukwu, Peter Dankelmann

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)

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 (δ+1n + 2)(n2) on the Wiener index of a graph of order n and minimum degree δ [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) ≤ (n-∆+2δ)nδ+2∆+1 + 2n(n - 1) on the Wiener index W(G) of a graph G of order n, minimum degree δ and maximum degree ∆. We prove a similar result for triangle-free graphs, and we determine a bound on the Wiener index of C4-free graphs of given order, minimum and maximum degree and show that it is, in some sense, best possible.

Original languageEnglish
JournalDiscrete Mathematics and Theoretical Computer Science
Volume23
Issue number1
DOIs
Publication statusPublished - 2021

Keywords

  • Average distance
  • Maximum degree
  • Mean distance
  • Minimum degree MSC-class: 05C12
  • Total distance
  • Wiener index

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Wiener index in graphs with given minimum degree and maximum degree'. Together they form a unique fingerprint.

Cite this