The complexity of obtaining a distance-balanced graph (Q540027)

Summary: An unweighted, connected graph is distance-balanced (also called self-median) if there exists a number \(d\) such that, for any vertex \(v\), the sum of the distances from \(v\) to all other vertices is \(d\). An unweighted connected graph is strongly distance-balanced (also called distance-degree regular) if there exist numbers \(d_1, d_2, d_3, \cdots \) such that, for any vertex \(v\), there are precisely \(d_k\) vertices at distance \(k\) from \(v\). We consider the following optimization problem: given a graph, add the minimum possible number of edges to obtain a (strongly) distance-balanced graph. We show that the problem is NP-hard for graphs of diameter three, thus answering the question posed by \textit{J. Jerebic, S. Klavžar} and \textit{D. F. Rall} [``Distance-balanced graphs,'' Ann. Comb. 12, No.\,1, 71--79 (2008; Zbl 1154.05026)]. In contrast, we show that the problem can be solved in polynomial time for graphs of diameter 2.