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'(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'(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.