On maximum Wiener index of trees and graphs with given radius

Kinkar Ch Das, M. J. Nadjafi-Arani

Research output: Contribution to journalArticlepeer-review

28 Scopus citations

Abstract

Let G be a connected graph of order n. The long-standing open and close problems in distance graph theory are: what is the Wiener index W(G) or average distance μ(G) among all graphs of order n with diameter d (radius r)? There are very few number of articles where were worked on the relationship between radius or diameter and Wiener index. In this paper, we give an upper bound on Wiener index of trees and graphs in terms of number of vertices n, radius r, and characterize the extremal graphs. Moreover, from this result we give an upper bound on μ(G) in terms of order and independence number of graph G. Also we present another upper bound on Wiener index of graphs in terms of number of vertices n, radius r and maximum degree Δ , and characterize the extremal graphs.

Original languageEnglish
Pages (from-to)574-587
Number of pages14
JournalJournal of Combinatorial Optimization
Volume34
Issue number2
DOIs
StatePublished - 1 Aug 2017

Keywords

  • Average distance
  • Graph
  • Maximum degree
  • Radius
  • Tree
  • Wiener index

Fingerprint

Dive into the research topics of 'On maximum Wiener index of trees and graphs with given radius'. Together they form a unique fingerprint.

Cite this