DEGREE DISTANCE AND MINIMUM DEGREE

Abstract

Abstract Let G be a finite connected graph of order n , minimum degree δ and diameter d . The degree distance D ′ ( G ) of G is defined as ∑ { u , v }⊆ V ( G ) (deg u +deg v ) d ( u , v ), where 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\biggl (n-\frac {d}{3}(\delta +1)\biggr )^2+O(n^3). \] As a corollary, we obtain the bound D ′ ( G )≤ n 4 /(9( δ +1) )+ O ( n 3 ) for a graph G of order n and minimum degree δ . This result, apart from improving on a result of Dankelmann et al . [‘On the degree distance of a graph’, Discrete Appl. Math. 157 (2009), 2773–2777] for graphs of given order and minimum degree, completely settles a conjecture of Tomescu [‘Some extremal properties of the degree distance of a graph’, Discrete Appl. Math. 98 (1999), 159–163].