Strongly distance-balanced graphs and graph products

A graph GG is strongly distance-balanced if for every edge uvuv of GG and every i≥0i≥0 the number of vertices xx with d(x,u)=d(x,v)−1=id(x,u)=d(x,v)−1=i equals the number of vertices yy with d(y,v)=d(y,u)−1=id(y,v)=d(y,u)−1=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 distance-balanced 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)O(mn) for their recognition, where mm is the number of edges and nn the number of vertices of the graph in question, are given.