On Extremal Cacti with Minimal Degree Distance

Abstract

Let $Diag(G)$ and $D(G)$ be the degree-diagonal matrix and distance matrix of $G$, respectively. Define the multiplier $Diag(G)D(G)$ as the degree distance matrix of $G$. The degree distance of $G$ is defined as $D^{\prime }(G)=\sum _{x\in V(G)}{d}_G(x)D(x)$, where $d_G(u)$ is the degree of vertex $x$, $D_G(x)=\sum _{u\in V(G)}{d}_G(u,x)$ and $d_G(u,x)$ is the distance between $u$ and $v$. Obviously, $D^{\prime }(G)$ is also the sum of elements of the degree distance matrix $Diag(G)D(G)$ of $G$. A connected graph $G$ is a cactus if any two of its cycles have at most one common vertex. Let $\mathcal{G}(n,r)$ be the set of cacti of order $n$ and with $r$ cycles. In this paper, we give the sharp lower bound of the degree distance of cacti among $\mathcal{G}(n,r)$, and characterize the corresponding extremal cactus.