Metric Dimension and R-Sets of Connected Graphs

Ioan Tomescu, Muhammad Imran

Research output: Contribution to journalArticlepeer-review

19 Citations (Scopus)

Abstract

The R-set relative to a pair of distinct vertices of a connected graph G is the set of vertices whose distances to these vertices are distinct. This paper deduces some properties of R-sets of connected graphs. It is shown that for a connected graph G of order n and diameter 2 the number of R-sets equal to V(G) is bounded above by {down left corner} n2/s{down right corner}. It is conjectured that this bound holds for every connected graph of order n. A lower bound for the metric dimension dim(G) of G is proposed in terms of a family of R-sets of G having the property that every subfamily containing at least r ≥ 2 members has an empty intersection. Three sufficient conditions, which guarantee that a family F=(Gn)n≥1 of graphs with unbounded order has unbounded metric dimension, are also proposed.

Original languageEnglish
Pages (from-to)585-591
Number of pages7
JournalGraphs and Combinatorics
Volume27
Issue number4
DOIs
Publication statusPublished - Jul 2011
Externally publishedYes

Keywords

  • Clique number
  • Diameter
  • Metric dimension
  • Resolving set

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Metric Dimension and R-Sets of Connected Graphs'. Together they form a unique fingerprint.

Cite this