Paper Info
Title
Moments in graphs
Abstract
Let G be a connected graph with vertex set V and a weight function@r that assigns a nonnegative number to each of its vertices. Then, the @r-moment of G at vertex u is defined to be M"G^@r(u)=@?"v"@?"V@r(v)dist(u,v), where dist(@?,@?) stands for the distance function. Adding up all these numbers, we obtain the @r-moment ofG: M"G^@r=@?u@?VMG@r(u)=12@?u,v@?Vdist(u,v)[@r(u)+@r(v)]. This parameter generalizes, or it is closely related to, some well-known graph invariants, such as the Wiener indexW(G), when @r(u)=1/2 for every u@?V, and the degree distanceD^'(G), obtained when @r(u)=@d(u), the degree of vertex u. In this paper we derive some exact formulas for computing the @r-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 @r-moments of its factors. As a consequence, we provide a method for obtaining nonisomorphic graphs with the same @r-moment for every @r (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.
Year
DOI
Venue
2013
10.1016/j.dam.2012.10.024
Discrete Applied Mathematics
Keywords
Field
DocType
degree distanced,r-moment ofg,equal mean distance,nonisomorphic graph,graft product,connected graph,hierarchical product,degree distance,vertex u,distance function,graph,moment,adjacency matrix,topological index
Adjacency matrix,Discrete mathematics,Linear algebra,Combinatorics,Wiener index,Vertex (geometry),Bound graph,Invariant (mathematics),Connectivity,Mathematics,Topological index
Journal
Volume
Issue
ISSN
161
6
0166-218X
Citations 
PageRank 
References 
1
0.36
16
Authors
3
Name
Order
Citations
PageRank
Cristina Dalfó1469.47
M. A. Fiol281687.28
E. Garriga316419.92