Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: The complexity of obtaining a distance-balanced graph. | The complexity of obtaining a distance-balanced graph Sergio Cabello Faculty of Mathematics and Physics University of Ljubljana and Institute of Mathematics Physics and Mechanics Jadranska 19 1000 Ljubljana Slovenia Primoz Luksic Faculty of Mathematics and Physics University of Ljubljana and Institute of Mathematics Physics and Mechanics Jadranska 19 1000 Ljubljana Slovenia Submitted Jul 20 2010 Accepted Feb 18 2011 Published Feb 28 2011 Mathematics Subject Classification 05C12 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 d1 d2 d3 . such that for any vertex v there are precisely dk 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. 1 Introduction For a graph G let dG u v denote the minimal path-length distance between vertices u and v of G. In this paper we restrict our attention to finite and connected graphs and thus the Research was supported by the Slovenian Research Agency program P1-0297. 1 Research was supported by the Slovenian Research Agency program P1-0294. THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P49 1 distances da - are always finite. Let us introduce the notation dG v VueV G dG u v for the sum of the distances in G from v to all other vertices. The median of a graph G is the set of all vertices v of G for which the value dG v is minimized. A .
