A graph G is strongly distance-balanced if for every edge uv of
G and every i 0 the number of vertices x with d.x; u/ D d.x; v/ 1 D i equals the number of vertices y with d.y; v/ D d.y; u/ 1 D i. It is proved that the strong product of graphs is
strongly distance-balanced if and only if both factors are strongly
distance-balanced. It is also proved that connected components of
the direct product of two bipartite graphs are strongly distancebalanced
if and only if both factors are strongly distance-balanced.
Additionally, a new characterization of distance-balanced graphs
and an algorithm of time complexity O.mn/ for their recognition,
wheremis the number of edges and n the number of vertices of the
graph in question, are given
Description:
European Journal of Combinatorics 30 (2009) 1048- 1053