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.