On some problems regarding distance-balanced graphs (Q2674566)

A graph \(G\) is distance-balanced when for any two adjacent vertices \(u\) and \(v\) of \(G\), \[ |W_{u,v}|=|W_{v,u}| \] where \(W_{x,y}\) denotes the set of the vertices of \(G\) that are closer to \(x\) than to \(y\). This metric property of graphs was first considered by \textit{K. Handa} [Ars Comb. 51, 113--119 (1999; Zbl 0977.05039)] and its name coined by \textit{J. Jerebic} et al. [Ann. Comb. 12, No. 1, 71--79 (2008; Zbl 1154.05026)]. Since the vertices \(u\) and \(v\) considered in the definition of distance-balancedness are adjacent, it follows from the triangle inequality that the distance to \(u\) of a vertex of \(G\) cannot differ by more than \(1\) from its distance to \(v\). In particular, \[ W_{u,v}=\bigcup_{i=1}^{d}\Bigl[S(u,i-1)\cap{S(v,i)}\Bigr] \] where \(S(x,i)\) denotes the set of the vertices of \(G\) distant by \(i\) from \(x\) (that can be considered a graph analogue of a sphere) and \(d\) the diameter of \(G\). The two stronger notions of nice distance-balancedness and of strong distance-balancedness can be defined as follows: \par i) nice distance-balancedness requires that \(|W_{u,v}|\) is the same for all the pairs of adjacent vertices \(u\) and \(v\) from \(G\) considered and \par ii) strong distance-balancedness asks that for all positive \(i\), \[ |S(u,i)\cap{S(v,i-1)}|=|S(u,i-1)\cap{S(v,i)}|. \] The article provides four results related to these three notions. First, the authors construct distance-balanced graphs that are neither bipartite nor strongly distance-balanced, answering a question by \textit{K. Kutnar} and \textit{Š. Miklavič} [Eur. J. Comb. 39, 57--67 (2014; Zbl 1284.05084)]. They construct two infinite families of such graphs, one of which is made up of regular graphs and the other of non-regular graphs. The former family is built by first exhibiting one graph with \(30\) vertices and then by using Cartesian products to construct an infinite family of them. If a graph \(G\) is strongly distance-balanced, then for any two adjacent vertices \(u\) and \(v\) of \(G\), the sum of the distances to \(u\) of the vertices in \(W_{u,v}\) coincides with the sum of the distances to \(v\) of the vertices in \(W_{v,u}\). It has been conjectured by \textit{K. Balakrishnan} et al. [Eur. J. Comb. 30, No. 5, 1048--1053 (2009; Zbl 1185.05052)] that the inverse implication also holds. Here, that conjecture is disproved using another infinite family of graphs. A graph is semi-symmetric when it is regular and edge-transitive but not vertex-transitive. \textit{K. Kutnar} et al. [Discrete Math. 306, No. 16, 1881--1894 (2006; Zbl 1100.05029)] have asked whether distance-balanced semi-symmetric graphs are always strongly distance-balanced. This question is answered negatively here, again by exhibiting adequate graphs. Finally, the authors show that strong distance-balancedness and nice distance-balancedness can each be decided in \(O(mn)\) time, where \(n\) is the number of vertices of the considered graph and \(m\) the number of its edges.