The complexity of obtaining a distance-balanced graph

Sergio Cabello ; Primož Lukšič

The electronic journal of combinatorics, Tome 18 (2011) no. 1

Résumé

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.

Détail

DOI : 10.37236/536

Classification : 05C12, 05C85
Mots-clés : distance balanced graph, self median graph, sum of distances, distance degree regular, optimization problem