\documentclass[12pt]{article}
\usepackage{amsmath,mathrsfs,bbm}
\usepackage{amssymb}
\textwidth=4.825in
\overfullrule=0pt
\thispagestyle{empty}

\begin{document}
\noindent
%
%
{\bf Sergio Cabello and Primo\v z Luk\v si\v c}
%
%

\medskip
\noindent
%
%
{\bf The Complexity of Obtaining a Distance-Balanced Graph}
%
%

\vskip 5mm
\noindent
%
%
%
%
An unweighted, connected graph is \emph{distance-balanced} (also
called \emph{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 \emph{strongly
distance-balanced} (also called \emph{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; \textsl{Ann. Comb.} 2008].  In
contrast, we show that the problem can be solved in polynomial time
for graphs of diameter 2.

\end{document}

.