# The Complexity of Obtaining a Distance-Balanced Graph

### Abstract

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,\dots$ 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 Jerebic et al. [Distance-balanced graphs; *Ann. Comb.* 2008]. In contrast, we show that the problem can be solved in polynomial time for graphs of diameter 2.