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

Abstract

This paper is concerned with the strong product of two graphs, and , 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 is a connected graph of given order and size, then the Wiener index of , for every fixed connected graph , and the Hosoya polynomial , for every with , are maximised if is a path-complete graph. We also investigate the average eccentricity of . We show that for fixed , and chosen from among all connected graphs of given order , it is maximised if is a path of the same order. We also determine a graph of order and minimum degree such that for every connected graph of order and minimum degree , the average eccentricity of never exceeds the average eccentricity of by more than 3.