Degree distance and minimum degree

Abstract

Let $G$ be a finite connected graph of order $n$, minimum degree $\delta$ and diameter $d$. The degree distance $D^\prime(G)$ of $G$ is defined as $\sum_{\{u,v\}\subseteq V(G)}({\rm deg}~ u+{\rm deg}~ v)d(u,v)$, where ${\rm deg}~ w$ is the degree of vertex $w$ and $d(u,v)$ denotes the distance between $u$ and $v$. In this paper, we find an asymptotically sharp upper bound on the degree distance in terms of order, minimum degree and diameter. In particular, we prove that $$D^\prime(G)\le \frac{1}{4}dn\left(n-\frac{d}{3}(\delta+1)\right)^2+O(n^3).$$ As a corollary, we obtain the bound $D^\prime(G)\le \frac{n^4}{9(\delta+1)}+O(n^3)$ for a graph $G$ of order $n$ and minimum degree $\delta$. This result, apart from improving on a result of Dankelmann, Gutman, Mukwembi and Swart [3] for graphs of given order and minimum degree, settles a conjecture of Tomescu [14] completely. Let \(G\) be a finite connected graph of order \(n\), minimum degree \(\delta\) and diameter \(d\). The degree distance \(D^\prime(G)\) of \(G\) is defined as \(\sum_{\{u,v\}\subseteq V(G)}(\operatorname{deg} u+\operatorname{deg}v)d(u,v)\), where \(\operatorname{deg}w\) is the degree of vertex \(w\) and \(d(u,v)\) denotes the distance between \(u\) and \(v\). In this paper, we find an asymptotically sharp upper bound on the degree distance in terms of order, minimum degree and diameter. In particular, we prove that \[D^\prime(G)\le \frac{1}{4}dn\left(n-\frac{d}{3}(\delta+1)\right)^2+O(n^3).\] As a corollary, we obtain the bound \(D^\prime(G)\le \frac{n^4}{9(\delta+1)}+O(n^3)\) for a graph \(G\) of order \(n\) and minimum degree \(\delta\). This result, apart from improving on a result of Dankelmann, Gutman, Mukwembi and Swart [3] for graphs of given order and minimum degree, settles a conjecture of Tomescu [14] completely. doi:10.1017/S0004972712000354