Computing the diversity vectors of balls of a given graph

摘要

For an ordinary finite not necessarily connected graph, thediversity vector of balls (ith component of the vector is equal to thenumber of different balls of radius i) is studied. Properties of metric ballsin such graphs are established. In particular, a coincidence condition ofballs with centers at different vertices is found. Based on these properties,the algorithm of computing the diversity vector of balls of a given graphG = (V;E) with a running time O(jV j3) is developed.