The Metric Dimension of Some Generalized Petersen Graphs

Abstract EN

The distance d(u,v) between two distinct vertices u and v in a graph G is the length of a shortest (u,v)-path in G.

For an ordered subset W={w1,w2,…,wk} of vertices and a vertex v in G, the code of v with respect to W is the ordered k-tuple cW(v)=(d(v,w1),d(v,w2),…,d(v,wk)).

The set W is a resolving set for G if every two vertices of G have distinct codes.

The metric dimension of G is the minimum cardinality of a resolving set of G.

In this paper, we first extend the results of the metric dimension of P(n,3) and P(n,4) and study bounds on the metric dimension of the families of the generalized Petersen graphs P(2k,k) and P(3k,k).

The obtained results mean that these families of graphs have constant metric dimension.