On the Number of Resolving Pairs in Graphs

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish
Pages (from-to)2175-2180
Number of pages6
JournalGraphs and Combinatorics
Issue number6
Publication statusPublished - 21 Jan 2015


  • Distance
  • Metric dimension
  • Resolving pair
  • Resolving set

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'On the Number of Resolving Pairs in Graphs'. Together they form a unique fingerprint.

Cite this