Total distance, Wiener index and opportunity index in wreath products of star graphs

Matteo Cavaleri¹ ; Alfredo Donno¹ ; Andrea Scozzari¹

¹University Niccolò Cusano - Roma

The electronic journal of combinatorics, Tome 26 (2019) no. 1

Résumé

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.

Détail

DOI : 10.37236/8071

Classification : 05C12, 05C57, 05C76