On the Local Adjacency Metric Dimension of Generalized Petersen Graphs


CAUCHY –Jurnal Matematika Murni dan Aplikasi 
Volume 6(1) (2019), Pages 10-17 
p-ISSN: 2086-0382; e-ISSN: 2477-3344 

Submitted: February 22, 2019 Reviewed: October 02, 2019 Accepted: November 30, 2019 
DOI: http://dx.doi.org/10.18860/ca.v6i1.6487  

On the Local Adjacency Metric Dimension of Generalized Petersen Graphs 

Marsidi1, Dafik2, Ika Hesti Agustin3, Ridho Alfarisi4 

1Mathematics Edu. Depart. IKIP PGRI Jember Indonesia 
2Mathematics Edu. Depart. University of Jember Indonesia 

3Mathematics Depart. University of Jember Indonesia 
4Elementary School Teacher Edu. Depart. University of Jember Indonesia 

 

Email: marsidiarin@gmail.com, d.dafik@gmail.com, ikahesti@fmipa.unej.ac.id. 

ABSTRACT 

The local adjacency metric dimension is one of graph topic. Suppose there are three neighboring 
vertex 𝑎, 𝑏, 𝑐 in path 𝑎 − 𝑐. Path 𝑎 − 𝑐 is called local if 𝑎,𝑏,𝑐 where each has representation: a is not 
equals 𝑏 and 𝑎 may equals to 𝑐. Let’s say, 𝑥,𝑦 ∈  𝑉(𝐺).  For an order set of vertices 𝐻 =
{ℎ1,ℎ2, . . . ,ℎ𝑘}, the adjacency representation of 𝑣 with respect to 𝐻 is the ordered 𝑘-tuple 
𝑟𝐴(𝑥𝑗|𝐻) = (𝑑𝐴(𝑥,ℎ1),𝑑𝐴(𝑥,ℎ2), . . . ,𝑑𝐴(𝑥,ℎ𝑘)), where 𝑑𝐴(𝑥,ℎ) represents the adjacency 

distance 𝑥 − ℎ. The distance 𝑑𝐴(𝑥,ℎ) defined by 0 if 𝑥 = ℎ𝑖, 1 if 𝑥 adjacent with ℎ, and 2 if 𝑥 
does not adjacent with ℎ. The set 𝐻 is a local adjacency resolving set of 𝐺 if for every two 
distinct vertices 𝑥, 𝑦 and 𝑥 adjacent with y then 𝑟𝐴(𝑥𝑗|𝐻) =𝑟𝐴(𝑦𝑗|𝐻). A minimum local 

adjacency resolving set in 𝐺 is called local adjacency metric basis. The cardinality of vertices in the 
basis is a local adjacency metric dimension of 𝐺, denoted by (𝑑𝑖𝑚𝐴,𝑙(𝐺)). Next, we investigate the 

local adjacency metric dimension of generalized Petersen graph. 

Keywords: Local Resolving Set; Local (Adjacency) Metric Dimension; Adjacency Metric 
Dimension; Generalized Petersen. 

INTRODUCTION 

A graph 𝐺 is defined by set of 𝑉(𝐺) and 𝐸(𝐺),  the set of vertices and the set of edges 
of 𝐺, for more details of  the definition in [1,2]. The metric dimension is one of interesting 
studied graph topics. Local means that every adjacent two vertices or two edges has 
distinct representation. Let’s say, there are three neighboring vertex in a path, 𝑎, 𝑏, 𝑐 
where each has representation: 𝑎 = 𝑏 and 𝑎 may equals 𝑐. Then, the path 𝑎 − 𝑐 is called 
local. The local adjacency metric dimension is combination of local metric dimension and 
adjacency metric dimension [3]. Let 𝐺 = (𝑉,𝐸) be a connected simple finite graph and 𝑢, 
𝑣 in 𝐺. For an ordered set of vertices 𝑋 = {𝑥1,𝑥2, . . . ,𝑥𝑘}, the adjacency representation of 
𝑣 with respect to 𝑋 is the ordered 𝑘-tuple 𝑟𝐴(𝑣|𝑋) = (𝑑𝐴(𝑣,𝑥1),𝑑𝐴(𝑣,𝑥2), . . . , 
𝑑_𝐴 (𝑣,𝑥_𝑘)), where 𝑑𝐴(𝑢,𝑣) represents the adjacency distance 𝑢 − 𝑣. 𝑑𝐴(𝑢,𝑣) defines by 
0 if 𝑢 = 𝑣𝑖, 1 if 𝑢 ∼ 𝑣, and 2 if 𝑢 ≉ 𝑣. We called 𝑋 is a local adjacency resolving set of G if 
for every two distinct vertices 𝑢, 𝑣 and 𝑢 ∼ 𝑣 then 𝑟𝐴(𝑢|𝑋) =𝑟𝐴(𝑣|𝑋). A local adjacency 
metric basis of G is a minimum local adjacency resolving set in G.  The cardinality of 
vertices in the basis is a local adjacency metric dimension of 𝐺(𝑑𝑖𝑚𝐴,𝑙(𝐺)). 

The research is originated by Rodriguez, et al. [3] about local adjacency metric 
dimension of corona graphs. Marsidi, et. al. Determined the local metric dimension of line 
graph of special graphs.  Then in 2017 Rinurwati, et al. [5] researched about local 
adjacency metric dimension of some wheel related graphs with pendant vertices.  

http://dx.doi.org/10.18860/ca.v6i1.6487
mailto:d.dafik@gmail.com


On the Local Adjacency Metric Dimension of Generalized Petersen Graphs 

Marsidi 11 

Recently, Darmaji, et al. [4] studied about local adjacency metric dimension of sun graph 
and stacked book graph this year. 

 

RESULTS AND DISCUSSION  

In this section, we investigate the local adjacency metric dimension of generalized 

Petersen graph 𝐺𝑃(𝑛,𝑘) for 𝑘 = 2 as follows 

Theorem 1. The local adjacency metric dimension of 𝐺𝑃(𝑛,2) is 𝑑𝑖𝑚𝐴,𝑙(𝐺𝑃(𝑛,2)) =
3𝑛+2

7
, for 𝑛 ≡ 4 𝑚𝑜𝑑 7. 

Proof. The vertex set of 𝐺𝑃(𝑛,2) is 𝑉(𝐺𝑃(𝑛,2)) = {𝑥𝑖,𝑦𝑖 ∶ 1 ≤  𝑖 ≤  𝑛}. We choose the 
local adjacensy resolving set 𝑊 = {𝑦𝑖;  𝑖 ≡  1 𝑚𝑜𝑑 7}⋃{𝑦𝑛 −2} such that we have the 
vertex representation respect to 𝐻 as follows. 
 
𝑟(𝑦𝑖|𝐻) = {2,2,…,2}, for 𝑖 ≡ 3 𝑚𝑜𝑑 7 

3𝑛+2

7
 

𝑟(𝑦𝑖|𝐻) = {2,2,…,2}, for 𝑖 ≡ 6 𝑚𝑜𝑑 7 

3𝑛+2

7
 

𝑟(𝑦𝑛−1|𝐻) = {2,2,…,2} 
3𝑛+2

7
 

𝑟(𝑦𝑛|𝐻) = {2,2,…,2} 

3𝑛+2

7
 

𝑟(𝑦𝑖|𝐻) = {2,2,…,2,1,2,2,…,2}, for 𝑖 ≡ 2 𝑚𝑜𝑑 7 

𝑖−2

7
             3𝑛−𝑖−3

7
 

𝑟(𝑦𝑖|𝐻) = {2,2,2,…,2,2,2,2,…,2,1,2,…,2,2,2,2,…,2,2,2}, for 𝑖 ≡ 4,5 𝑚𝑜𝑑 7 

𝑖−3

7
                    𝑖−2

7
          3𝑛−𝑖−3

7
               3𝑛−𝑖−4

7
 

𝑟(𝑦𝑖|𝐻) = {2,2,2,…,2,2,2,2,…,2,1,2,…,2,2,2,2,…,2,2,2}, for 𝑖 ≡ 0 𝑚𝑜𝑑 7 

𝑖−3

7
                   𝑖−2

7
           3𝑛−𝑖−3

7
               3𝑛−𝑖−4

7
 

 
The representation in vertex 𝑥𝑖 ∈ 𝑉(𝐺𝑃(𝑛,2)) follows the representation in vertex 

𝑦𝑖 such that we have the cardinality of local adjacency resolving set is |𝐻| = |{𝑣𝑖; 𝑖 ≡

1 𝑚𝑜𝑑 7} ∪{𝑣𝑛−2}| =
3𝑛+2

7
. Thus, the upper bound of local adjacency metric dimension of 

𝐺𝑃(𝑛,2) is 𝑑𝑖𝑚𝐴,𝑙(𝐺𝑃(𝑛,2)) ≤
3𝑛+2

7
. Furthermore, we prove that the lower bound of local 

adjacency metric dimension of 𝐺𝑃(𝑛,2) is 𝑑𝑖𝑚𝐴,𝑙(𝐺𝑃(𝑛,2)) ≥
3𝑛+2

7
. Assume that 

𝑑𝑖𝑚𝐴,𝑙(𝐺𝑃(𝑛,2)) <
3𝑛+2

7
, we choose |𝐻| =

3𝑛+2

7
− 1 such that we have the same 

representation for two adjacent vertices in 𝐺𝑃(𝑛,2) namely 𝑟(𝑦𝑛|𝐻) ≠ 𝑟(𝑦𝑛−2|𝐻) =. 

{2,…,2}⏟    

(
3𝑛−5

7
)

. Thus, the local adjacency metric dimension of 𝐺𝑃(𝑛,2) is 𝑑𝑖𝑚𝐴,𝑙(𝐺𝑃(𝑛,2)) =
3𝑛+2

7
, 

for 𝑛 ≡ 4 𝑚𝑜𝑑 7. ∎ 

Theorem 2. The local adjacency metric dimension of 𝐺𝑃(𝑛,2) is 𝑑𝑖𝑚𝐴,𝑙(𝐺𝑃(𝑛,2)) =
3𝑛+6

7
, 

for 𝑛 ≡ 5 𝑚𝑜𝑑 7. 



On the Local Adjacency Metric Dimension of Generalized Petersen Graphs 

Marsidi 12 

Proof. The vertex set of 𝐺𝑃(𝑛,2) is 𝑉(𝐺𝑃(𝑛,2)) = {𝑥𝑖,𝑦𝑖 ∶ 1 ≤  𝑖 ≤  𝑛}. We choose the 
local adjacency resolving set 𝐻 = {𝑦𝑖;  𝑖 ≡  1 𝑚𝑜𝑑 7}⋃{𝑦𝑛 −2} such that we have the 
vertex representation respect to 𝐻 as follows. 
 
𝑟(𝑦𝑖|𝐻) = {2,2,…,2}, for 𝑖 ≡ 3 𝑚𝑜𝑑 7 

3𝑛+2

7
 

𝑟(𝑦𝑖|𝐻) = {2,2,…,2}, for 𝑖 ≡ 6 𝑚𝑜𝑑 7 

3𝑛+2

7
 

𝑟(𝑦𝑛−1|𝐻) = {2,2,…,2} 

3𝑛+2

7
 

𝑟(𝑦𝑛|𝐻) = {2,2,…,2} 
3𝑛+2

7
 

𝑟(𝑦𝑖|𝐻) = {2,2,…,2,1,2,2,…,2}, for 𝑖 ≡ 2 𝑚𝑜𝑑 7 

𝑖−2

7
             3𝑛−𝑖−3

7
 

𝑟(𝑦𝑖|𝐻) = {2,2,2,…,2,2,2,2,…,2,1,2,…,2,2,2,2,…,2,2,2}, for 𝑖 ≡ 4,5 𝑚𝑜𝑑 7 

𝑖−3

7
                 𝑖−2

7
              3𝑛−𝑖−3

7
               3𝑛−𝑖−4

7
 

𝑟(𝑦𝑖|𝐻) = {2,2,2,…,2,2,2,2,…,2,1,2,…,2,2,2,2,…,2,2,2}, for 𝑖 ≡ 0 𝑚𝑜𝑑 7 

𝑖−3

7
                 𝑖−2

7
              3𝑛−𝑖−3

7
               3𝑛−𝑖−4

7
 

 
The representation in vertex 𝑥𝑖 ∈ 𝑉(𝐺𝑃(𝑛,2)) follows the representation in vertex 

𝑦𝑖 such that we have the cardinality of local adjacency resolving set is |𝐻| = |{𝑦𝑖; 𝑖 ≡

1 𝑚𝑜𝑑 7} ∪{𝑦𝑛−2}| =
3𝑛+6

7
. Thus, the upper bound of local adjacency metric dimension of 

𝐺𝑃(𝑛,2) is 𝑑𝑖𝑚𝐴,𝑙(𝐺𝑃(𝑛,2)) ≤
3𝑛+6

7
. Furthermore, we prove that the lower bound of local 

adjacency metric dimension of 𝐺𝑃(𝑛,2) is 𝑑𝑖𝑚𝐴,𝑙(𝐺𝑃(𝑛,2)) ≥
3𝑛+6

7
. Assume that 

𝑑𝑖𝑚𝐴,𝑙(𝐺𝑃(𝑛,2)) <
3𝑛+6

7
, we choose |𝐻| =

3𝑛+6

7
− 1 such that we have the same 

representation for two adjacent vertices in 𝐺𝑃(𝑛,2) namely 𝑟(𝑦𝑛|𝐻) ≠ 𝑟(𝑦𝑛−2|𝐻) =

{2,…,2}⏟    

(
3𝑛−5

7
)

. Thus, the local adjacency metric dimension of 𝐺𝑃(𝑛,2) is 𝑑𝑖𝑚𝐴,𝑙(𝐺𝑃(𝑛,2))=
3𝑛+6

7
,  

for 𝑛 ≡ 5 𝑚𝑜𝑑 7. ∎ 
 

Theorem 3. The local adjacency metric dimension of 𝐺𝑃(𝑛,2) is 𝑑𝑖𝑚𝐴,𝑙(𝐺𝑃(𝑛,2)) =
3𝑛+3

7
, 

for 𝑛 ≡ 6 𝑚𝑜𝑑 7. 
Proof. The vertex set of 𝐺𝑃(𝑛,2) is 𝑉(𝐺𝑃(𝑛,2)) = {𝑥𝑖,𝑦𝑖 ∶ 1 ≤  𝑖 ≤  𝑛}. We choose the 
local adjacency resolving set 𝐻 = {𝑦𝑖;  𝑖 ≡  1 𝑚𝑜𝑑 7}⋃{𝑦𝑛 −2} such that we have the 
vertex representation respect to 𝐻 as follows. 

𝑟(𝑦𝑖|𝐻) = {2,2,…,2}, for 𝑖 ≡ 3 𝑚𝑜𝑑 7 

3𝑛+2

7
 

𝑟(𝑦𝑖|𝐻) = {2,…,2}⏟    

(
3𝑛+2

7
)

, for 𝑖 ≡ 6 𝑚𝑜𝑑 7 

𝑟(𝑦𝑛−1|𝐻) = {2,2,…,2} 



On the Local Adjacency Metric Dimension of Generalized Petersen Graphs 

Marsidi 13 

3𝑛+2

7
 

𝑟(𝑦𝑛|𝐻) = {2,2,…,2} 
3𝑛+2

7
 

𝑟(𝑦𝑖|𝐻) = {2,2,…,2,1,2,2,…,2}, for 𝑖 ≡ 2 𝑚𝑜𝑑 7 

  𝑖−2
7

               3𝑛−𝑖−3
7

 

𝑟(𝑦𝑖|𝐻) = {2,2,2,…,2,2,2,2,…,2,1,2,…,2,2,2,2,…,2,2,2}, for 𝑖 ≡ 4,5 𝑚𝑜𝑑 7 

𝑖−3

7
                   𝑖−2

7
            3𝑛−𝑖−3

7
             3𝑛−𝑖−4

7
 

𝑟(𝑦𝑖|𝐻) = {2,2,2,…,2,2,2,2,…,2,1,2,…,2,2,2,2,…,2,2,2}, for 𝑖 ≡ 0 𝑚𝑜𝑑 7 

𝑖−3

7
                   𝑖−2

7
           3𝑛−𝑖−3

7
               3𝑛−𝑖−4

7
 

 
The representation in vertex 𝑥𝑖 ∈ 𝑉(𝐺𝑃(𝑛,2)) follows the representation in vertex 

𝑦𝑖 such that we have the cardinality of local adjacency resolving set is |𝐻| = |{𝑦𝑖; 𝑖 ≡

1 𝑚𝑜𝑑 7} ∪{𝑦𝑛−2}| =
3𝑛+3

7
. Thus, the upper bound of local adjacency metric dimension of 

𝐺𝑃(𝑛,2) is 𝑑𝑖𝑚𝐴,𝑙(𝐺𝑃(𝑛,2)) ≤
3𝑛+3

7
. Furthermore, we prove that the lower bound of local 

adjacency metric dimension of 𝐺𝑃(𝑛,2) is 𝑑𝑖𝑚𝐴,𝑙(𝐺𝑃(𝑛,2)) ≥
3𝑛+3

7
. Assume that 

𝑑𝑖𝑚𝐴,𝑙(𝐺𝑃(𝑛,2)) <
3𝑛+3

7
, we choose |𝐻| =

3𝑛+3

7
− 1 such that we have the same 

representation for two adjacent vertices in  𝐺𝑃(𝑛,2) namely  𝑟(𝑦𝑛|𝐻) ≠ 𝑟(𝑦𝑛−2|𝐻) =

{2,…,2}⏟    

(
3𝑛−5

7
)

. Thus, the local adjacency metric dimension of 𝐺𝑃(𝑛,2) is 𝑑𝑖𝑚𝐴,𝑙(𝐺𝑃(𝑛,2)) =
3𝑛+3

7
, 

for 𝑛 ≡ 6 𝑚𝑜𝑑 7. ∎ 
 

Theorem 4. The local adjacency metric dimension of 𝐺𝑃(𝑛,2) is 𝑑𝑖𝑚𝐴,𝑙(𝐺𝑃(𝑛,2)) =
3𝑛

7
, 

for 𝑛 ≡ 0 𝑚𝑜𝑑 7. 

Proof. The vertex set of 𝐺𝑃(𝑛,2) is 𝑉(𝐺𝑃(𝑛,2)) = {𝑥𝑖,𝑦𝑖 ∶ 1 ≤  𝑖 ≤  𝑛}. We choose the 
local adjacency resolving set 𝐻 = {𝑦𝑖;  𝑖 ≡  1 𝑚𝑜𝑑 7}⋃{𝑦𝑛 −2} such that we have the 
vertex representation respect to 𝐻 as follows. 

𝑟(𝑦𝑖|𝐻) = {2,2,…,2}, for 𝑖 ≡ 3 𝑚𝑜𝑑 7 

3𝑛+2

7
 

𝑟(𝑦𝑖|𝐻) = {2,2,…,2}, for 𝑖 ≡ 6 𝑚𝑜𝑑 7 

3𝑛+2

7
 

𝑟(𝑦𝑛−1|𝐻) = {2,2,…,2} 
3𝑛+2

7
 

𝑟(𝑦𝑛|𝐻) = {2,2,…,2} 
3𝑛+2

7
 

 
𝑟(𝑦𝑖|𝐻) = {2,2,…,2,1,2,2,…,2}, for 𝑖 ≡ 2 𝑚𝑜𝑑 7 

 𝑖−2
7

                3𝑛−𝑖−3
7

 

𝑟(𝑦𝑖|𝐻) = {2,2,2,…,2,2,2,2,…,2,1,2,…,2,2,2,2,…,2,2,2}, for 𝑖 ≡ 4,5 𝑚𝑜𝑑 7 



On the Local Adjacency Metric Dimension of Generalized Petersen Graphs 

Marsidi 14 

 𝑖−3
7

                  𝑖−2
7

            3𝑛−𝑖−3
7

             3𝑛−𝑖−4
7

 

𝑟(𝑦𝑖|𝐻) = {2,2,2,…,2,2,2,2,…,2,1,2,…,2,2,2,2,…,2,2,2}, for 𝑖 ≡ 0 𝑚𝑜𝑑 7 

 𝑖−3
7

                  𝑖−2
7

            3𝑛−𝑖−3
7

             3𝑛−𝑖−4
7

 

 
The representation in vertex 𝑥𝑖 ∈ 𝑉(𝐺𝑃(𝑛,2)) follows the representation in vertex 

𝑦𝑖 such that we have the cardinality of local adjacency resolving set is |𝐻| = |{𝑦𝑖; 𝑖 ≡

1 𝑚𝑜𝑑 7} ∪{𝑦𝑛−2}| =
3𝑛+2

7
. Thus, the upper bound of local adjacency metric dimension of 

𝐺𝑃(𝑛,2) is 𝑑𝑖𝑚𝐴,𝑙(𝐺𝑃(𝑛,2)) ≤
3𝑛

7
. Furthermore, we prove that the lower bound of local 

adjacency metric dimension of 𝐺𝑃(𝑛,2) is 𝑑𝑖𝑚𝐴,𝑙(𝐺𝑃(𝑛,2)) ≥
3𝑛

7
. Assume that 

𝑑𝑖𝑚𝐴,𝑙(𝐺𝑃(𝑛,2)) <
3𝑛

7
, we choose |𝐻| =

3𝑛

7
− 1 such that we have the same representation 

for two adjacent vertices in 𝐺𝑃(𝑛,2) namely 𝑟(𝑦𝑛|𝐻) ≠ 𝑟(𝑦𝑛−2|𝐻) = {2,…,2}⏟    

(
3𝑛−5

7
)

. Thus, the 

local adjacency metric dimension of 𝐺𝑃(𝑛,2) is 𝑑𝑖𝑚𝐴,𝑙(𝐺𝑃(𝑛,2))=
3𝑛

7
, for 𝑛 ≡ 0 𝑚𝑜𝑑 7. 

∎ 
 

Theorem 5. The local adjacency metric dimension of 𝐺𝑃(𝑛,2) is 𝑑𝑖𝑚𝐴,𝑙(𝐺𝑃(𝑛,2)) =
3𝑛+4

7
, 

for 𝑛 ≡ 1 𝑚𝑜𝑑 7. 

Proof. The vertex set of 𝐺𝑃(𝑛,2) is 𝑉(𝐺𝑃(𝑛,2)) = {𝑥𝑖,𝑦𝑖 ∶ 1 ≤  𝑖 ≤  𝑛}. We choose the 
local adjacency resolving set 𝐻 = {𝑦𝑖;  𝑖 ≡  1 𝑚𝑜𝑑 7}⋃{𝑦𝑛 −2} such that we have the 
vertex representation respect to 𝐻 as follows. 

𝑟(𝑦𝑖|𝐻) = {2,2,…,2}, for 𝑖 ≡ 3 𝑚𝑜𝑑 7 
3𝑛+2

7
 

𝑟(𝑦𝑖|𝐻) = {2,2,…,2}, for 𝑖 ≡ 6 𝑚𝑜𝑑 7 
3𝑛+2

7
 

𝑟(𝑦𝑛−1|𝐻) = {2,2,…,2} 
3𝑛+2

7
 

𝑟(𝑦𝑛|𝐻) = {2,2,…,2} 

  3𝑛+2
7

 

𝑟(𝑦𝑖|𝐻) = {2,2,…,2,1,2,2,…,2}, for 𝑖 ≡ 2 𝑚𝑜𝑑 7 

 𝑖−2
7

                3𝑛−𝑖−3
7

 

𝑟(𝑦𝑖|𝐻) = {2,2,2,…,2,2,2,2,…,2,1,2,…,2,2,2,2,…,2,2,2}, for 𝑖 ≡ 4,5 𝑚𝑜𝑑 7 

𝑖−3

7
                   𝑖−2

7
           3𝑛−𝑖−3

7
              3𝑛−𝑖−4

7
 

𝑟(𝑦𝑖|𝐻 ) = {2,2,2,…,2,2,2,2,…,2,1,2,…,2,2,2,2,…,2,2,2}, for 𝑖 ≡ 0 𝑚𝑜𝑑 7 

𝑖−3

7
                   𝑖−2

7
            3𝑛−𝑖−3

7
             3𝑛−𝑖−4

7
 

 
The representation in vertex 𝑥𝑖 ∈ 𝑉(𝐺𝑃(𝑛,2)) follows the representation in vertex 

𝑦𝑖 such that we have the cardinality of local adjacency resolving set is |𝐻| = |{𝑦𝑖; 𝑖 ≡

1 𝑚𝑜𝑑 7} ∪{𝑦𝑛−2}| =
3𝑛+4

7
. Thus, the upper bound of local adjacency metric dimension of 

𝐺𝑃(𝑛,2) is 𝑑𝑖𝑚𝐴,𝑙(𝐺𝑃(𝑛,2)) ≤
3𝑛+4

7
. Furthermore, we prove that the lower bound of local 



On the Local Adjacency Metric Dimension of Generalized Petersen Graphs 

Marsidi 15 

adjacency metric dimension of 𝐺𝑃(𝑛,2) is 𝑑𝑖𝑚𝐴,𝑙(𝐺𝑃(𝑛,2)) ≥
3𝑛+4

7
. Assume that 

𝑑𝑖𝑚𝐴,𝑙(𝐺𝑃(𝑛,2)) <
3𝑛+4

7
, we choose |𝐻| =

3𝑛

7
− 1 such that we have the same 

representation for two adjacent vertices in  𝐺𝑃(𝑛,2) namely  𝑟(𝑦𝑛|𝐻) ≠ 𝑟(𝑦𝑛−2|𝐻) =

{2,…,2}⏟    

(
3𝑛−5

7
)

. Thus, the local adjacency metric dimension of 𝐺𝑃(𝑛,2) is 𝑑𝑖𝑚𝐴,𝑙(𝐺𝑃(𝑛,2))= 
3𝑛+4

7
, 

for 𝑛 ≡ 1 𝑚𝑜𝑑 7. ∎ 
 

Theorem 6. The local adjacency metric dimension of 𝐺𝑃(𝑛,2) is 𝑑𝑖𝑚𝐴,𝑙(𝐺𝑃(𝑛,2)) =
3𝑛+1

7
, 

for 𝑛 ≡ 2 𝑚𝑜𝑑 7. 

Proof. The vertex set of 𝐺𝑃(𝑛,2) is 𝑉(𝐺𝑃(𝑛,2)) = {𝑥𝑖,𝑦𝑖 ∶ 1 ≤  𝑖 ≤  𝑛}. We choose the 
local adjacency resolving set 𝐻 = {𝑦𝑖;  𝑖 ≡  1 𝑚𝑜𝑑 7}⋃{𝑦𝑛 −2} such that we have the 
vertex representation respect to 𝐻 as follows. 

𝑟(𝑦𝑖|𝐻) = {2,2,…,2}, for 𝑖 ≡ 3 𝑚𝑜𝑑 7 
3𝑛+2

7
 

𝑟(𝑦𝑖|𝐻) = {2,2,…,2}, for 𝑖 ≡ 6 𝑚𝑜𝑑 7 
3𝑛+2

7
 

𝑟(𝑦𝑛−1|𝐻) = {2,2,…,2} 
3𝑛+2

7
 

𝑟(𝑦𝑛|𝐻) = {2,2,…,2} 

3𝑛+2

7
 

𝑟(𝑦𝑖|𝐻) = {2,2,…,2,1,2,2,…,2}, for 𝑖 ≡ 2 𝑚𝑜𝑑 7 

 𝑖−2
7

                3𝑛−𝑖−3
7

 

𝑟(𝑦𝑖|𝐻) = {2,2,2,…,2,2,2,2,…,2,1,2,…,2,2,2,2,…,2,2,2}, for 𝑖 ≡ 4,5 𝑚𝑜𝑑 7 

𝑖−3

7
                   𝑖−2

7
            3𝑛−𝑖−3

7
             3𝑛−𝑖−4

7
 

𝑟(𝑦𝑖|𝐻) = {2,2,2,…,2,2,2,2,…,2,1,2,…,2,2,2,2,…,2,2,2}, for 𝑖 ≡ 0 𝑚𝑜𝑑 7 

𝑖−3

7
                   𝑖−2

7
            3𝑛−𝑖−3

7
             3𝑛−𝑖−4

7
 

 
The representation in vertex 𝑥𝑖 ∈ 𝑉(𝐺𝑃(𝑛,2)) follows the representation in vertex 

𝑦𝑖 such that we have the cardinality of local adjacency resolving set is |𝐻| = |{𝑦𝑖; 𝑖 ≡

1 𝑚𝑜𝑑 7} ∪{𝑦𝑛−2}| =
3𝑛+1

7
. Thus, the upper bound of local adjacency metric dimension of 

𝐺𝑃(𝑛,2) is 𝑑𝑖𝑚𝐴,𝑙(𝐺𝑃(𝑛,2)) ≤
3𝑛+1

7
. Furthermore, we prove that the lower bound of local 

adjacency metric dimension of 𝐺𝑃(𝑛,2) is 𝑑𝑖𝑚𝐴,𝑙(𝐺𝑃(𝑛,2)) ≥
3𝑛+1

7
. Assume that 

𝑑𝑖𝑚𝐴,𝑙(𝐺𝑃(𝑛,2)) <
3𝑛+1

7
, we choose |𝐻| =

3𝑛+1

7
− 1 such that we have the same 

representation for two adjacent vertices in  𝐺𝑃(𝑛,2) namely  𝑟(𝑦𝑛|𝐻) ≠ 𝑟(𝑦𝑛−2|𝐻) =

{2,…,2}⏟    

(
3𝑛−5

7
)

. Thus, the local adjacency metric dimension of 𝐺𝑃(𝑛,2) is 𝑑𝑖𝑚𝐴,𝑙(𝐺𝑃(𝑛,2))= 
3𝑛+1

7
, 

for 𝑛 ≡ 2 𝑚𝑜𝑑 7. ∎ 
 



On the Local Adjacency Metric Dimension of Generalized Petersen Graphs 

Marsidi 16 

Theorem 7. The local adjacency metric dimension of 𝐺𝑃(𝑛,2) is 𝑑𝑖𝑚𝐴,𝑙(𝐺𝑃(𝑛,2)) =
3𝑛−2

7
, 

for 𝑛 ≡ 3 𝑚𝑜𝑑 7. 

Proof. The vertex set of 𝐺𝑃(𝑛,2) is 𝑉(𝐺𝑃(𝑛,2)) = {𝑥𝑖,𝑦𝑖 ∶ 1 ≤  𝑖 ≤  𝑛}. We choose the 
local adjacency resolving set 𝐻 = {𝑦𝑖;  𝑖 ≡  1 𝑚𝑜𝑑 7}⋃{𝑦𝑛 −2} such that we have the 
vertex representation respect to 𝐻 as follows. 

𝑟(𝑦𝑖|𝐻) = {2,2,…,2}, for 𝑖 ≡ 3 𝑚𝑜𝑑 7 
3𝑛+2

7
 

𝑟(𝑣𝑖|𝐻) = {2,2,…,2}, for 𝑖 ≡ 6 𝑚𝑜𝑑 7 

3𝑛+2

7
 

𝑟(𝑦𝑛−1|𝐻) = {2,2,…,2} 
3𝑛+2

7
 

𝑟(𝑦𝑛|𝐻) = {2,2,…,2} 
3𝑛+2

7
 

𝑟(𝑦𝑖|𝐻) = {2,2,…,2,1,2,2,…,2}, for 𝑖 ≡ 2 𝑚𝑜𝑑 7 

  𝑖−2
7

               3𝑛−𝑖−3
7

 

𝑟(𝑦𝑖|𝐻) = {2,2,2,…,2,2,2,2,…,2,1,2,…,2,2,2,2,…,2,2,2}, for 𝑖 ≡ 4,5 𝑚𝑜𝑑 7 

𝑖−3

7
                   𝑖−2

7
            3𝑛−𝑖−3

7
             3𝑛−𝑖−4

7
 

𝑟(𝑦𝑖|𝐻) = {2,2,2,…,2,2,2,2,…,2,1,2,…,2,2,2,2,…,2,2,2}, for 𝑖 ≡ 0 𝑚𝑜𝑑 7 

𝑖−3

7
                   𝑖−2

7
            3𝑛−𝑖−3

7
             3𝑛−𝑖−4

7
 

 
The representation in vertex 𝑥𝑖 ∈ 𝑉(𝐺𝑃(𝑛,2)) follows the representation in vertex 

𝑦𝑖 such that we have the cardinality of local adjacency resolving set is |𝐻| = |{𝑦𝑖; 𝑖 ≡

1 𝑚𝑜𝑑 7} ∪{𝑦𝑛−2}| =
3𝑛−2

7
. Thus, the upper bound of local adjacency metric dimension of 

𝐺𝑃(𝑛,2) is 𝑑𝑖𝑚𝐴,𝑙(𝐺𝑃(𝑛,2)) ≤
3𝑛−2

7
. Furthermore, we prove that the lower bound of local 

adjacency metric dimension of 𝐺𝑃(𝑛,2) is 𝑑𝑖𝑚𝐴,𝑙(𝐺𝑃(𝑛,2)) ≥
3𝑛−2

7
. Assume that 

𝑑𝑖𝑚𝐴,𝑙(𝐺𝑃(𝑛,2)) <
3𝑛−2

7
, we choose |𝐻| =

3𝑛−2

7
− 1 such that we have the same 

representation for two adjacent vertices in  𝐺𝑃(𝑛,2) namely  𝑟(𝑦𝑛|𝐻) ≠ 𝑟(𝑦𝑛−2|𝐻) =

{2,…,2}⏟    

(
3𝑛−5

7
)

. Thus, the local adjacency metric dimension of 𝐺𝑃(𝑛,2) is 𝑑𝑖𝑚𝐴,𝑙(𝐺𝑃(𝑛,2))= 
3𝑛−2

7
, 

for 𝑛 ≡ 3 𝑚𝑜𝑑 7. ∎ 
 

CONCLUSIONS 

We have discussed about the local adjacency metric dimension of generalized 
Petersen graph 𝐺𝑃(𝑛,𝑘) for 𝑘 = 2. Accordingly, we have some problem for 𝑘 ≥ 3 as 
follows.  

 
Open Problem 1. Find the local adjacency metric dimension of generalized Petersen 
graph 𝐺𝑃(𝑛,𝑘) for 𝑘 ≥ 3 ?. 

 



On the Local Adjacency Metric Dimension of Generalized Petersen Graphs 

Marsidi 17 

ACKNOWLEDGMENTS  

We gratefully acknowledge the support from IKIP PGRI Jember 2019 and CGANT-
University of Jember of year 2019. 

 

REFERENCES 

 

[1]  J. L. Gross, J. Yellen and P. Zhang, Handbook of graph Theory, Second Edition CRC 
Press Taylor and Francis Group, 2014. 

[2]  G. Chartrand and L. Lesniak, Graphs and digraphs 3rd ed London: Chapman and Hall, 
2000. 

[3]  J. A. Rodriguez-Velazquez and H. Fernau, " On the (adjacency) metric dimension of 
corona and strong product graphs and their local variants", Combinatorial and 

Computational Results, Arxiv: 1309.2275.v1[math.CO]. 

[4]  A. Y. Badri and Darmaji, ”Local adjacency metric dimension of sun graph and stacked 
book graph”,  Journal of Physics: Conf. Series, vol. 974, No. 012069, pp. 01-05, 2018. 

[5] 
 
 
[6]  

Rinurwati, H. Suprajitno, and Slamin, ”On local adjacency metric dimension of some 
wheel related graphs with pendant points”,  AIP Conference Proceedings, vol. 1867, No. 
020065, pp. 01-06, 2017. 
Marsidi, M., Dafik, D., Agustin, I. H., & Alfarisi, R. (2016). On the local metric  
dimension of line graph of special graph. Cauchy, 4(3), 125-130.