Moments in graphs

Let G be a connected graph with vertex set V and a weight function rho that assigns a nonnegative number to each of its vertices. Then, the rho-moment of G at vertex u is defined to be M-G(rho) (u) = Sigma(vEV) rho(v)dist(u, v), where dist(.,.) stands for the distance function. Adding up all these numbers, we obtain the rho-moment of G: M-G(rho) = Sigma(u is an element of V) M-G(rho)(u) = 1/2 Sigma(u,v is an element of V) dist(u, v)[rho(u) + rho(v)]. This parameter generalizes, or it is closely related to, some well-known graph invariants, such as the Wiener index W (G), when rho(u) = 1/2 for every u is an element of V, and the degree distance D'(G), obtained when rho(u) = delta(u), the degree of vertex u. In this paper we derive some exact formulas for computing the rho-moment of a graph obtained by a general operation called graft product, which can be seen as a generalization of the hierarchical product, in terms of the corresponding rho-moments of its factors. As a consequence, we provide a method for obtaining nonisomorphic graphs with the same rho-moment for every rho (and hence with equal mean distance, Wiener index, degree distance, etc.). In the case when the factors are trees and/or cycles, techniques from linear algebra allow us to give formulas for the degree distance of their product. (C) 2012 Elsevier B.V. All rights reserved.