Graphs with distinguishing sets of size k

Abstract

The size of a resolving set R of a non-trivial connected graph Γ of order n ≥ 2 is the number of edges in the induced subgraph .The minimum cardinality of a resolving set of size k of graph Γ is called the metric dimension of size k, denoted by β(k)(Γ). We study the existence of resolving sets of size k in some families of graphs and investigate their properties. We find bounds on the metric dimension of size k of a graph Γ. We give the necessary condition for the metric dimension of size k and size (k + 1) of a graph Γ, to satisfy the inequality β(k+1)(Γ) − β(k)(Γ) ≤ 1. We will disprove a conjecture on bounds of the metric dimension of size k. For every positive integers k, l, and n such that k + 1 ≤ l ≤ n, we give a realizable result of a graph Γ of order n and l = β(k)(Γ).

Keywords

• induced subgraph
• metric dimension
• metric dimension of size k
• resolving set
• resolving set of size k