## 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} n^{2}/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=(G_{n})_{n≥1} of graphs with unbounded order has unbounded metric dimension, are also proposed.

Original language | English |
---|---|

Pages (from-to) | 585-591 |

Number of pages | 7 |

Journal | Graphs and Combinatorics |

Volume | 27 |

Issue number | 4 |

DOIs | |

Publication status | Published - Jul 2011 |

Externally published | Yes |

## Keywords

- Clique number
- Diameter
- Metric dimension
- Resolving set

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics