Ordering connected graphs having small degree distances
The concept of degree distance of a connected graph G G is a variation of the well-known Wiener index, in which the degrees of vertices are also involved. It is defined by D?(G)=?x?V(G)d(x)?y?V(G)d(x,y) D ? ( G ) = ? x ? V ( G ) d ( x ) ? y ? V ( G ) d ( x , y ) , where d(x) d ( x ) and d(x,y) d ( x , y ) are the degree of x x and the distance between x x and y y , respectively. In this paper it is proved that connected graphs of order n?4 n ? 4 having the smallest degree distances are K1,n?1,BS(n?3,1) K 1 , n ? 1 , B S ( n ? 3 , 1 ) and K1,n?1+e K 1 , n ? 1 + e (in this order), where BS(n?3,1) B S ( n ? 3 , 1 ) denotes the bistar consisting of vertex disjoint stars K1,n?3 K 1 , n ? 3 and K1,1 K 1 , 1 with central vertices joined by an edge.
degree distance bistar eccentricity diameter tree