The Metric Dimension of Some Generalized Petersen Graphs

Authors:

Open Access

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 = {w_{1}, w_{2}, \dots, w_{k}}

of vertices and a vertex

v

G

, the code of

v

with respect to

W

is the ordered

k

-tuple

c_{W} (v) = (d (v, w_{1}), d (v, w_{2}), \dots, d (v, w_{k}))

. 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 (2 k, k)

and

P (3 k, k)

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

National key research and development program (2017YFB0802300, 17ZA0079, 18ZA0118, 2018ZR0265, 2017JY0095)
Education Department of Sichuan Province (2017YFB0802300, 17ZA0079, 18ZA0118, 2018ZR0265, 2017JY0095)
Education Department of Sichuan Province (2017YFB0802300, 17ZA0079, 18ZA0118, 2018ZR0265, 2017JY0095)
Soft Scientific Research Foundation of Sichuan Provincial Science and Technology Department (2017YFB0802300, 17ZA0079, 18ZA0118, 2018ZR0265, 2017JY0095)
Applied Basic Research (Key Project) of Sichuan Province (2017YFB0802300, 17ZA0079, 18ZA0118, 2018ZR0265, 2017JY0095)

This publication has 22 references indexed in Scilit: