On the Harary Index of Cacti


Zhongxun Zhu, Ting Tao, Jing Yu, Liansheng Tan




The Harary index is defined as the sum of reciprocals of distances between all pairs of vertices of a connected graph. A connected graph $G$ is a cactus if any two of its cycles have at most one common vertex. Let $\Cal G(n,r)$ be the set of cacti of order $n$ and with $r$ cycles, $\xi(2n,r)$ the set of cacti of order $2n$ with a perfect matching and $r$ cycles. In this paper, we give the sharp upper bounds of the Harary index of cacti among $\Cal G(n,r)$ and $\xi(2n,r)$, respectively, and characterize the corresponding extremal cactus.