Strongly distance-balanced graphs and graph products (Q1024301)

A graph \(G\) is distance-balanced if for every edge \(uv\in E(G)\), \[ \left|\left\{x\mid d(u,x) < d(v,x)\right\}\right| = \left|\left\{x\mid d(v,x) < d(u,x)\right\}\right|, \] where \(d(u,v)\) is the length of a shortest path between \(u\) and \(v\) in \(G\). \(G\) is strongly distance-balanced if for every edge \(uv\in E(G)\) and every \(i\geq 0\) the number of vertices \(x\in V(G)\) with \(d(x,u)=d(x,v)-1=i\) equals the number of vertices \(y\in V(G)\) with \(d(y,v)= d(y,u)-1=i\). The vertex set of the Cartesian product/the direct product/the strong product of two graphs \(G\) and \(H\) is \(V(G)\times V(H)\). In the Cartesian product \(G\square H\) two vertices are adjacent if they are adjacent in one coordinate and equal in the other. In the direct product \(G\times H\) two vertices are adjacent if they are adjacent in both coordinates. The edge set of the strong product \(G\boxtimes H\) is the union of \(E(G\square H)\) and \(E(G\times H)\). The results of the paper are: {\parindent=6mm \begin{itemize}\item[(1)]\(G\boxtimes H\) is strongly distance-balanced if and only if \(G\) and \(H\) are strongly distance-balanced. \item[(2)]Let \(G\) and \(H\) be connected bipartite graphs. Then the connected components of \(G\times H\) are strongly distance-balanced if and only if \(G\) and \(H\) are strongly distance-balanced. \item[(3)]A connected graph \(G\) is distance-balanced if and only if \(M(G)=V(G)\), where \(M(G)\) is the set of all vertices \(x\) of \(G\) for which \(\sum_{v\in V(G)} d(x,v)\) is minimal among all vertices of \(G\). \end{itemize}} It follows from (3) that recognizing if a graph \(G\) is distance-balanced can be done in \(O\left(|V(G)|\cdot |E(G)|\right)\) time.