Distance and Eccentric sequences to bound the Wiener index, Hosoya polynomial and the average eccentricity in the strong products of graphs

Rocío M. Casablanca, Peter Dankelmann

Research output: Contribution to journalArticlepeer-review

12 Citations (Scopus)

Abstract

This paper is concerned with the strong product G⊠H of two graphs, G and H, and bounds on the Wiener index, Hosoya polynomial and the average eccentricity in this family of graphs. We first introduce the distance sequence of a connected graph. It is defined as the sequence of the distances between all unordered pairs of vertices. We prove that the distance sequence of any connected graph of given order and size is dominated by the distance sequence of the so-called path-complete graph. This is the main tool to prove general results as, among others, that, if G is a connected graph of given order and size, then the Wiener index of G⊠H, for every fixed connected graph H, and the Hosoya polynomial W(G,x), for every x∈R with x≥1, are maximised if G is a path-complete graph. We also investigate the average eccentricity of G⊠H. We show that for fixed H, and G chosen from among all connected graphs of given order n, it is maximised if G is a path of the same order. We also determine a graph Gn,δ of order n and minimum degree δ such that for every connected graph G of order n and minimum degree δ, the average eccentricity of G⊠H never exceeds the average eccentricity of Gn,δ⊠H by more than 3.

Original languageEnglish
Pages (from-to)105-117
Number of pages13
JournalDiscrete Applied Mathematics
Volume263
DOIs
Publication statusPublished - 30 Jun 2019

Keywords

  • Average distance
  • Average eccentricity
  • Distance distribution
  • Distance sequence
  • Hosoya polynomial
  • Strong product
  • Wiener index
  • Wiener polynomial

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Distance and Eccentric sequences to bound the Wiener index, Hosoya polynomial and the average eccentricity in the strong products of graphs'. Together they form a unique fingerprint.

Cite this