## 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 G_{n,δ} 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 G_{n,δ}⊠H by more than 3.

Original language | English |
---|---|

Pages (from-to) | 105-117 |

Number of pages | 13 |

Journal | Discrete Applied Mathematics |

Volume | 263 |

DOIs | |

Publication status | Published - 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