Strongly distance-balanced graphs and graph products

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