Total Distance, Wiener Index and Opportunity Index in Wreath Products of Star Graphs

  • Matteo Cavaleri
  • Alfredo Donno
  • Andrea Scozzari


In the last decades much attention has turned towards centrality measures on graphs. The Wiener index and the total distance are key tools to investigate the median vertices, the distance-balanced property and the opportunity index of a graph. This interest has recently been addressed to graphs obtained via classical graph products like the Cartesian, the direct, the strong and the lexicographic product. We extend this study to a relatively new graph product, that is, the wreath product. In this paper, we compute the total distance for the vertices of an arbitrary wreath product graph $G\wr H$ in terms of the total distances in $H$ and of some distance-based indices of $G$. We explicitly compute these indices for the star graph $S_n$, providing a closed formula for the total distances in $S_n\wr H$ when $H$ is complete or a star. As a consequence, we obtain the Wiener index of these graphs, we characterize the median and the central vertices, and finally we give an upper and a lower bound for the opportunity index of $S_n\wr S_m$ in terms of tail conditional expectations of an associated binomial distribution.

Article Number