On the Number of Resolving Pairs in Graphs

Let G be a connected graph. An unordered pair {x,y} of vertices of G is a resolving pair if no vertex of G has the same distance to x and y. It was conjectured in [8] that the number of resolving pairs of a connected graph of order n is bounded above by ⌊n24⌋. In this note we show that there exists a constant c>0 such that for sufficiently large n every graph of order n contains at most n2-cn3/2 resolving pairs. We further show that the exponent 3/2 is best possible by exhibiting an infinite sequence of graphs with at least n2-cn3/2logn resolving pairs, where c is a positive constant, thus disproving the above conjecture.