On the Metric Dimension of Some Operation Graphs


CAUCHY –Jurnal Matematika Murni dan Aplikasi 
Volume 5(3) (2018), Pages 88-94 
p-ISSN: 2086-0382; e-ISSN: 2477-3344 

Submitted: 23 July 2018 Reviewed: 08 October 2018 Accepted: 30 November 2018 
DOI: http://dx.doi.org/10.18860/ca.v5i3.5331 
 

On the Metric Dimension of Some Operation Graphs 

Marsidi1, Ika Hesti Agustin2, Dafik3, Ridho Alfarisi4, Hendrik Siswono5 

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

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

5Majoring in Early Childhood Edu. Depart. IKIP PGRI Jember Indonesia 
 

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

ABSTRACT 

Let 𝐺 be a simple, finite, and connected graph. An ordered set of vertices of a nontrivial connected 
graph 𝐺 is 𝑊 = {𝑤1,𝑤2,𝑤3,…,𝑤𝑘} and the 𝑘-vector 𝑟(𝑣|𝑊) = (𝑑(𝑣,𝑤1),𝑑(𝑣,𝑤2),…,𝑑(𝑣,𝑤𝑘)) 

represent vertex 𝑣 that respect to 𝑊, where 𝑣 ∈ 𝐺 and 𝑑(𝑣,𝑤𝑖) is the distance between vertex 𝑣 
and 𝑤𝑖 for 1 ≤ 𝑖 ≤ 𝑘. The set 𝑊 called a resolving set for 𝐺 if different vertex of 𝐺 have different 
representations that respect to 𝑊. The minimum cardinality of resolving set of 𝐺 is the metric 
dimension of 𝐺, denoted by dim⁡(𝐺). In this paper, we give the local metric dimension of some 
operation graphs such as joint graph 𝑃𝑛 + 𝐶𝑚, amalgamation of parachute, amalgamation of fan, 
and 𝑠ℎ𝑎𝑐𝑘(𝐻2

2,𝑒,𝑚). 

Keywords: metric dimension, resolving set, operation graphs. 

INTRODUCTION 

All graphs in this paper are simple, finite and connected, for basic definition of 
graph we can see in Chartrand [1]. Chartrand [2] define the length of a shortest path 
between two vertices 𝑢 and 𝑣 is the distance 𝑑(𝑢,𝑣) between two vertices in a connected 
graph G. An ordered set of vertices of a nontrivial connected graph 𝐺 is 𝑊 =
{𝑤1,𝑤2,𝑤3,…,𝑤𝑘} and the 𝑘-vector 𝑟(𝑣|𝑊) = (𝑑(𝑣,𝑤1),𝑑(𝑣,𝑤2),…,𝑑(𝑣,𝑤𝑘)) represent 

vertex 𝑣 that respect to 𝑊. The set 𝑊 called a resolving set for 𝐺 if different vertex of 𝐺 
have different representations that respect to 𝑊. The minimum of cardinality of resolving 
set of G is the metric dimension of 𝐺, denoted by dim(𝐺) [3].  

There are many articles explained about metric dimension such as [2], [4], [5], [6], 
and [7]. [8] defined a shackle graphs 𝑠ℎ𝑎𝑐𝑘(𝐺1,𝐺2,…,𝐺𝑘) constructed by nontrivial 
connected graphs 𝐺1,𝐺2,…,𝐺𝑘 such that 𝐺𝑖 and 𝐺𝑗 have no a common vertex for every 

𝑖, 𝑗 ∈ [1,𝑘] with |𝑖 − 𝑗| ≥ 2, and for every 𝑙 ∈ [1,𝑘 − 1], 𝐺𝑙 and 𝐺𝑙+1 share exactly one 
common vertex (called linkage vertex) and the 𝑘 − 1 linking vertices are all different. [9] 
defined an amalgamation of graphs constructed from isomorphic connected graphs 𝐻 and 
the choice of the vertex 𝑣𝑗 as a terminal is irrelevant. For any 𝑘 positive integer, we denote 

such an amalgamation by 𝑎𝑚𝑎𝑙(𝐻,𝑘), where 𝑘 denotes the number of copies of 𝐻. 
Proposition 1. [2] Let 𝐺 be a connected graph or order 𝑛⁡ ≥ ⁡2, then the following hold: 

a. 𝑑𝑖𝑚(𝐺) = 1⁡if and only if graph 𝐺 is a path graph 

b. 𝑑𝑖𝑚(𝐺) = 𝑛 − 1 if and only if graph 𝐺 is a complete graph 

c. For 𝑛 ≥ 3, 𝑑𝑖𝑚(𝐶𝑛) = 2 

mailto:marsidiarin@gmail.com,%20ikahesti@fmipa.unej.ac.id
mailto:d.dafik@gmail.com


On the Metric Dimension of Some Operation Graphs 

Marsidi 89 

d. For 𝑛 ≥ 4, 𝑑𝑖𝑚(𝐺) = 𝑛 − 2 if and only if 𝐺 = 𝐾𝑝,𝑞⁡(𝑝,𝑞 ≥ 1),𝐺 =

𝐾𝑝 + 𝐾𝑞̅̅̅̅ (𝑝 ≥ 1,𝑞 ≥ 2).  

RESULTS AND DISCUSSION  

Theorem 2.1. For 𝑛 ≥ 2 and 𝑚 ≥ 7, the metric dimension of joint graph 𝑃𝑛 + 𝐶𝑚 is 

𝑑𝑖𝑚(𝑃𝑛 + 𝐶𝑚) = ⌈
𝑛

2
⌉⁡+⁡⌊

𝑚−1

2
⌋. 

Proof. The joint of path and cycle graph, denoted by 𝑃𝑛 + 𝐶𝑚 is a connected graph with 
vertex set 𝑉(𝑃𝑛 + 𝐶𝑚) = {𝑥𝑗; ⁡1 ≤ 𝑗 ≤ 𝑛} ∪ {𝑦𝑙; ⁡1 ≤ 𝑙 ≤ 𝑚} and edge set 𝐸(𝑃𝑛 + 𝐶𝑚) =

{𝑥𝑗𝑦𝑙; ⁡1 ≤ 𝑗 ≤ 𝑛; ⁡1 ≤ 𝑙 ≤ 𝑚} ∪ {𝑥𝑗𝑥𝑗+1; ⁡1 ≤ 𝑗 ≤ 𝑛 − 1} ∪ {𝑦𝑙𝑦𝑙+1; ⁡1 ≤ 𝑙 ≤ 𝑚 − 1} ∪
{𝑦𝑛𝑦1}. The cardinality of vertex set and edge set, respectively are |𝑉(𝑃𝑛 + 𝐶𝑚)|⁡= ⁡𝑛⁡ +
⁡𝑚 and |𝐸(𝑃𝑛 + 𝐶𝑚)| = ⁡𝑛(𝑚 + 1) + 𝑚. 

 If we show that 𝑑𝑖𝑚(𝑃𝑛 + 𝐶𝑚) = ⌈
𝑛

2
⌉⁡+⁡⌊

𝑚−1

2
⌋ for 𝑛⁡ ≥ 2 dan 𝑚 ≥ 7, then we will 

show the lower bound namely 𝑑𝑖𝑚(𝑃𝑛 + 𝐶𝑚) ≥ ⌈
𝑛

2
⌉⁡+⁡⌊

𝑚−1

2
⌋ − 1. Assume that 𝑑𝑖𝑚(𝑃𝑛 +

𝐶𝑚) < ⌈
𝑛

2
⌉⁡+⁡⌊

𝑚−1

2
⌋. This can be shown with take resolving set 𝑊 = {𝑥1,𝑦1,𝑦5} so that it 

obtained the representation of the vertices 𝑥,𝑦 ∈ 𝑉(𝑃2 + 𝐶7) respect to 𝑊. 
 It can be seen that there is at least two vertices in 𝑃𝑛 + 𝐶𝑚 which have the same 
representation respect to 𝑊, one of them is 𝑟(𝑦4|𝑊)⁡= (1,2,1) and 𝑟(𝑦6|𝑊)⁡= (1,2,1) 

such that we have the cardinality of resolving set of 𝑑𝑖𝑚(𝑃𝑛 + 𝐶𝑚) ≥ ⌈
𝑛

2
⌉⁡+⁡⌊

𝑚−1

2
⌋. 

 Furthermore, we will prove that 𝑑𝑖𝑚(𝑃𝑛 + 𝐶𝑚) ≤ ⌈
𝑛

2
⌉⁡+⁡⌊

𝑚−1

2
⌋ with determine the 

resolving set 𝑊 = {𝑥𝑗; ⁡1 ≤ 𝑗 ≤ 2⌊
𝑛

2
⌋ ; ⁡𝑖 ∈ 𝑜𝑑𝑑} ∪ {𝑦𝑙; ⁡1 ≤ 𝑙 ≤ 2⌊

𝑚−1

2
⌋ ; ⁡𝑗 ∈ 𝑜𝑑𝑑}. So, we 

have the cardinality of resolving set of 𝑃𝑛 + 𝐶𝑚 namely |𝑊| =
2⌈
𝑛
2
⌉

2
⁡+

2⌈
𝑚−1
2
⌉

2
= ⌊

𝑛

2
⌋ + ⌊

𝑚−1

2
⌋. 

The representation of the vertices 𝑦 ∈ 𝐹𝑛 and 𝑥 ∈ 𝐹𝑛 respect to 𝑊 as follows. 

𝑟(𝑥𝑗|𝑊)⁡=⁡{(𝑎𝑖𝑗); ⁡1 ≤ 𝑗 ≤ 𝑛,1 ≤ 𝑖 ≤ (⌈
𝑛

2
⌉ + 1) + (⌊

𝑚−1

2
⌋)}, where 

𝑎𝑖𝑗 =

{
 
 

 
 0;𝑓𝑜𝑟⁡𝑖 =

𝑗+1

2
,1 ≤ 𝑗 ≤ 𝑛,𝑗 ∈ 𝑜𝑑𝑑⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡

1;𝑓𝑜𝑟⁡(⌈
𝑛

2
⌉ + 1) ≤ 𝑖 ≤ (⌈

𝑛

2
⌉ + 1) + (⌊

𝑚−1

2
⌋) ,1 ≤ 𝑗 ≤ 𝑛⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡

𝑜𝑟⁡𝑖 =
𝑗

2
,2 ≤ 𝑗 ≤ 𝑛,𝑗 ∈ 𝑒𝑣𝑒𝑛⁡𝑜𝑟⁡𝑖 =

𝑗

2
+ 1,2 ≤ 𝑗 ≤ 𝑛,𝑗 ∈ 𝑒𝑣𝑒𝑛

2;𝑓𝑜𝑟⁡𝑖, 𝑗 = 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡

 

 𝑟(𝑦𝑙|𝑊) = {(𝑎𝑖𝑗); ⁡1 ≤ 𝑗 ≤ 𝑚,1 ≤ 𝑖 ≤ (⌈
𝑛

2
⌉ + 1) + (⌊𝑚−1

2
⌋)}, where 

𝑎𝑖𝑗 =

{
 
 
 

 
 
 0;𝑓𝑜𝑟⁡𝑖 = (⌈

𝑛

2
⌉) +

𝑗+1

2
,1 ≤ 𝑗 ≤ 𝑚 − 2,𝑗 ∈ 𝑜𝑑𝑑

1;𝑓𝑜𝑟⁡1 ≤ 𝑖 ≤ (⌈
𝑛

2
⌉) ,1 ≤ 𝑗 ≤ 𝑚 − 2⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡

𝑜𝑟⁡𝑖 = (⌈
𝑛

2
⌉) +

𝑗

2
,2 ≤ 𝑗 ≤ 𝑚,𝑗 ∈ 𝑒𝑣𝑒𝑛⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡

𝑜𝑟⁡𝑖 = (⌈
𝑛

2
⌉) +

𝑗+1

2
+ 1,2 ≤ 𝑗 ≤ 𝑚,𝑗 ∈ 𝑒𝑣𝑒𝑛⁡⁡⁡⁡

2;𝑓𝑜𝑟⁡𝑖, 𝑗 = 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡

 

 
It can be seen that every vertex in 𝑃𝑛 + 𝐶𝑚 have distinct representation respect to 

𝑊, such that the cardinality of resolvng set in 𝑃𝑛 + 𝐶𝑚 is ⌈
𝑛

2
⌉⁡+⁡⌊

𝑚−1

2
⌋ or 𝑑𝑖𝑚(𝐹𝑛) ≤ ⌈

𝑛

2
⌉⁡+

⁡⌊
𝑚−1

2
⌋. Thus, we conclude that 𝑑𝑖𝑚(𝑃𝑛 + 𝐶𝑚)⁡=⁡⌈

𝑛

2
⌉⁡+⁡⌊

𝑚−1

2
⌋ for 𝑛 ≥ 2 and 𝑚 ≥ 7. ∎ 



On the Metric Dimension of Some Operation Graphs 

Marsidi 90 

 

 
 

Fig 1. The Metric Dimension of Joint Graph 𝑃6 + 𝐶4. 
 

Theorem 2.2. For 𝑛 ≥ 7, the metric dimension of amalgamation of parachute 

𝑎𝑚𝑎𝑙⁡(𝑃𝐶7,𝑣,𝑚) is 𝑑𝑖𝑚(𝑎𝑚𝑎𝑙(𝑃𝐶7,𝑣 = 𝐴,𝑚)) =
6𝑚

2
. 

Proof. The amalgamation of parasut graph, denoted by 𝑎𝑚𝑎𝑙(𝑃𝐶7,𝑣,𝑚) is a connected 

graph with vertex set 𝑉(𝑎𝑚𝑎𝑙(𝑃𝐶7,𝑣,𝑚)) = {𝑥𝑖
𝑗
; ⁡1 ≤ 𝑖 ≤ 7; ⁡1 ≤ 𝑗 ≤ 𝑚} ∪ {𝑦𝑖

𝑗
; ⁡1 ≤ 𝑖 ≤

7; ⁡1 ≤ 𝑗 ≤ 𝑚} ∪ {𝐴} and edge set 𝐸(𝑎𝑚𝑎𝑙(𝑃𝐶7,𝑣,𝑚)) = {𝐴⁡𝑥𝑖
𝑗
; ⁡1 ≤ 𝑖 ≤ 7; ⁡1 ≤ 𝑗 ≤ 𝑚} ∪

{⁡𝑥𝑖
𝑗
⁡𝑥𝑖+1
𝑗
; ⁡1 ≤ 𝑖 ≤ 6; ⁡1 ≤ 𝑗 ≤ 𝑚} ∪ {⁡𝑦𝑖

𝑗
⁡𝑦𝑖+1
𝑗
; ⁡1 ≤ 𝑖 ≤ 6; ⁡1 ≤ 𝑗 ≤ 𝑚} ∪ {⁡𝑥1

𝑗
⁡𝑦1
𝑗
; ⁡1 ≤ 𝑗 ≤

𝑚} ∪ {⁡𝑥7
𝑗
⁡𝑦7
𝑗
; ⁡1 ≤ 𝑗 ≤ 𝑚}. The cardinality of vertex set and edge set, respectively are 

|𝑉(𝑎𝑚𝑎𝑙(𝑃𝐶7,𝑣,𝑚))|⁡= 14m⁡ + ⁡1 and |𝐸(𝑎𝑚𝑎𝑙(𝑃𝐶7,𝑣,𝑚))|⁡= ⁡21𝑚. 
  

If we show that 𝑑𝑖𝑚(𝑎𝑚𝑎𝑙(𝑃𝐶7,𝑣,𝑚)) ≥
6𝑚

2
r 𝑛⁡ = ⁡7, then we will show the best 

lower bound namely 𝑑𝑖𝑚(𝑎𝑚𝑎𝑙(𝑃𝐶7,𝑣,𝑚)) ≥
7𝑚

2
− 1. Assume that 

𝑑𝑖𝑚(𝑎𝑚𝑎𝑙(𝑃𝐶7,𝑣,𝑚)) <
6𝑚

2
.⁡This can be shown with take resolving set 𝑊 =

{𝑥1
1,𝑥4

1,𝑥6
1,𝑥1

2,𝑥4
2,𝑥6

2,𝑥1
3,𝑥4

3,𝑥6
3,𝑥1

4,𝑥4
4,𝑥6

4} so that it obtained the representation of the 
vertices 𝑥,𝑦 ∈ 𝑉(𝑎𝑚𝑎𝑙(𝑃𝐶7,𝑣,𝑚)) respect to 𝑊. It can be seen that there is at least two 
vertices in 𝑎𝑚𝑎𝑙(𝑃𝐶7,𝑣,4) which have the same representation respect to 𝑊, one of them 
is 𝑟(𝑥3

1|𝑊)⁡= (2,1,2,2,2,2,2,2,2,2,2) and 𝑟(𝑥5
1|𝑊)⁡= (2,1,2,2,2,2,2,2,2,2,2) such 

that we have the cardinality of resolving set of (𝑎𝑚𝑎𝑙(𝑃𝐶7,𝑣,𝑚)) ≥ ⌈
6𝑚

2
⌉. 

Furthermore, we will prove that 𝑑𝑖𝑚(𝑎𝑚𝑎𝑙(𝑃𝐶7,𝑣,𝑚)) ≤ ⌈
6𝑚

2
⌉ with determine the 

resolving set 𝑊 = {𝑥𝑖
𝑗
; ⁡4 ≤ 𝑖 ≤ 7; ⁡2 ≤ 𝑗 ≤ 𝑚;⁡𝑖 = 𝑜𝑑𝑑} ∪ {𝑥1

𝑗
; ⁡1 ≤ 𝑗 ≤ 𝑚}. So, we have 

the cardinality of resolving set of 𝑎𝑚𝑎𝑙(𝑃𝐶7,𝑣,𝑚) namely |𝑊|⁡=⁡|{𝑥𝑖
𝑗
; ⁡4 ≤ 𝑖 ≤ 7; ⁡2 ≤

𝑗 ≤ 𝑚;𝑖 = 𝑜𝑑𝑑} ∪ {𝑥1
𝑗
;1 ≤ 𝑗 ≤ 𝑚}| = (

4

2
𝑚)⁡+ 𝑚 = (

6𝑚

2
). The representation of the 

vertices 𝑦 ∈ (𝑎𝑚𝑎𝑙(𝑃𝐶7,𝑣,𝑚 = 4)) and 𝑥 ∈ (𝑎𝑚𝑎𝑙(𝑃𝐶7,𝑣,𝑚 = 4)) respect to 𝑊 as 

follows. 

𝑟(𝑥𝑖
𝑗
|𝑊) = {(𝑎𝑖𝑘

𝑗
); ⁡1 ≤ 𝑖 ≤ 𝑛,1 ≤ 𝑗 ≤ 𝑚,1 ≤ 𝑘 ≤

6𝑚

2
}, where 

𝑎𝑖𝑘 =

{
 
 

 
 0;𝑓𝑜𝑟⁡𝑘 = 1,𝑘 = 2𝑖,2 ≤ 𝑖 ≤ (⌊

𝑛

2
⌋) ,1 ≤ 𝑗 ≤ 𝑚⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡

1;𝑓𝑜𝑟⁡𝑘 =
𝑖+1

2
,3 ≤ 𝑖 ≤ 𝑛,𝑖 ∈ 𝑜𝑑𝑑⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡

1 ≤ 𝑗 ≤ 𝑚⁡𝑜𝑟⁡𝑘 =
𝑖−1

2
,5 ≤ 𝑖 ≤ 7,𝑖 ∈ 𝑜𝑑𝑑,1 ≤ 𝑗 ≤ 𝑚

2;𝑓𝑜𝑟⁡1 ≤ 𝑗 ≤ 𝑚,𝑘,𝑖 = 𝑜𝑡ℎ𝑒𝑟⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡

 



On the Metric Dimension of Some Operation Graphs 

Marsidi 91 

 𝑟(𝑦|𝑊) = {(𝑎𝑖𝑘); ⁡1 ≤ 𝑖 ≤ 7,1 ≤ 𝑘 ≤
6𝑚+2

2
}, where 

𝑎𝑖𝑘 =

{
 
 
 
 
 
 
 
 

 
 
 
 
 
 
 
 
1;𝑓𝑜𝑟⁡𝑘 = 3𝑗 − 2,𝑖 = 1,1 ≤ 𝑗 ≤ 𝑚⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡

2;𝑓𝑜𝑟⁡𝑘 =
6𝑚+2

2
, 𝑖 = 1,7,1 ≤ 𝑗 ≤ 𝑚⁡𝑜𝑟⁡𝑘 = 3𝑗 − 2,𝑖 = 2,⁡⁡⁡⁡⁡⁡⁡⁡⁡

1 ≤ 𝑗 ≤ 𝑚⁡𝑜𝑟⁡𝑘 = 3𝑗, 𝑖 = 7,1 ≤ 𝑗 ≤ 𝑚⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡

3; ⁡𝑓𝑜𝑟⁡𝑘 =
6𝑚+2

2
, 𝑖 = 2,6,1 ≤ 𝑗 ≤ 𝑚⁡𝑜𝑟⁡𝑘 = 3𝑗 − 2,𝑖 = 3,⁡⁡⁡⁡⁡⁡⁡⁡

1 ≤ 𝑗 ≤ 𝑚⁡𝑜𝑟⁡𝑘 = 3𝑗, 𝑖 = 6,1 ≤ 𝑗 ≤ 𝑚⁡𝑜𝑟⁡𝑖 = 1,⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡

𝑘 ≠ 3𝑗 − 2⁡𝑎𝑛𝑑⁡𝑘 =
6𝑚+2

2
⁡𝑜𝑟⁡𝑖 = 7,𝑘 ≠ 3𝑗⁡𝑎𝑛𝑑⁡𝑘 =

6𝑚+2

2
⁡⁡⁡⁡⁡⁡⁡⁡⁡

4; ⁡𝑓𝑜𝑟⁡𝑘 =
6𝑚+2

2
, 𝑖 = 3,5,1 ≤ 𝑗 ≤ 𝑚⁡𝑜𝑟⁡𝑘 = 3𝑗 − 2,𝑖 = 4,⁡⁡⁡⁡⁡⁡⁡⁡

1 ≤ 𝑗 ≤ 𝑚⁡𝑜𝑟⁡𝑘 = 3𝑗, 𝑖 = 5,1 ≤ 𝑗 ≤ 𝑚⁡𝑜𝑟⁡𝑖 = 2,⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡

𝑘 ≠ 3𝑗 − 2⁡𝑎𝑛𝑑⁡𝑘 =
6𝑚+2

2
⁡𝑜𝑟⁡𝑖 = 6,𝑘 ≠ 3𝑗⁡𝑎𝑛𝑑⁡𝑘 =

6𝑚+2

2
⁡⁡⁡⁡⁡⁡⁡⁡⁡

5; ⁡𝑓𝑜𝑟⁡𝑘 =
6𝑚+2

2
, 𝑖 = 3,3𝑗⁡𝑜𝑟⁡𝑘 ≠ 3𝑗 − 2⁡𝑎𝑛𝑑⁡𝑘 ≠

6𝑚+2

2
, 𝑖 = 3,

𝑜𝑟⁡𝑘 ≠ 3𝑗⁡𝑎𝑛𝑑⁡𝑘 ≠
6𝑚+2

2
, 𝑖 = 5⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡

6;𝑓𝑜𝑟⁡𝑖 = 4⁡𝑎𝑛𝑑⁡𝑖 ≠ 3𝑗⁡𝑎𝑛𝑑⁡𝑖 ≠ 3𝑗 − 2⁡𝑎𝑛𝑑⁡𝑖 ≠
6𝑚+2

2
⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡

 

 
It can be seen that every vertex in 𝑎𝑚𝑎𝑙(𝑃𝐶7,𝑣,𝑚) have distinct representation 

respect to 𝑊, such that the cardinality of resolvng set in 𝑎𝑚𝑎𝑙(𝑃𝐶7,𝑣,𝑚) is 
6𝑚

2
 or 

𝑑𝑖𝑚(𝑎𝑚𝑎𝑙(𝑃𝐶7,𝑣,𝑚)) ≤
6𝑚

2
. Thus, we conclude that 𝑑𝑖𝑚(𝑎𝑚𝑎𝑙(𝑃𝐶7,𝑣,𝑚))⁡=⁡

6𝑚

2
. ∎ 

 
Fig 2. The Metric Dimension of Amalgamation of Parachute 𝐴𝑚𝑎𝑙⁡(𝑃𝐶7,𝑣,3). 

 
Theorem 2.3. For 𝑛 ≥ 6, the metric dimension of amalgamation of fan graph 
𝑎𝑚𝑎𝑙(𝐹𝑛,𝑣 = 𝑦,𝑚) is: 



On the Metric Dimension of Some Operation Graphs 

Marsidi 92 

𝑑𝑖𝑚(𝑎𝑚𝑎𝑙(𝐹𝑛,𝑣 = 𝐴,𝑚)) = {

𝑛𝑚

2
− 1,𝑓𝑜𝑟⁡𝑛⁡is⁡even

𝑛𝑚 − 𝑚

2
,𝑓𝑜𝑟⁡𝑛⁡is⁡odd⁡⁡⁡⁡

 

Proof. The amalgamation of fan graph, denoted by 𝑎𝑚𝑎𝑙(𝐹𝑛,𝑣 = 𝑦,𝑚) is a connected 

graph with vertex set 𝑉(𝑎𝑚𝑎𝑙(𝐹𝑛,𝑣 = 𝑦,𝑚)) = {𝑥𝑖
𝑗
; ⁡1 ≤ 𝑖 ≤ 𝑛 − 1; ⁡1 ≤ 𝑗 ≤ 𝑚} ∪

{𝑦𝑗; ⁡1 ≤ 𝑗 ≤ 𝑚} ∪ {𝑥𝑛
𝑚} and edge set 𝐸(𝑎𝑚𝑎𝑙(𝐹𝑛,𝑣 = 𝑦,𝑚)) = {⁡𝑥𝑖

𝑗
⁡𝑥𝑖+1
𝑗
; ⁡1 ≤ 𝑖 ≤ 𝑛 −

2; ⁡1 ≤ 𝑗 ≤ 𝑚} ∪ {𝑦𝑗𝑥𝑖
𝑗
; ⁡1 ≤ 𝑖 ≤ 𝑛 − 1; ⁡1 ≤ 𝑗 ≤ 𝑚} ∪ {⁡𝑥𝑛−1

𝑗
⁡𝑥1
𝑗+1
; ⁡1 ≤ 𝑗 ≤ 𝑚 − 1} ∪

{⁡𝑥𝑛−1
𝑚 ⁡𝑥𝑛

𝑚} ∪ {𝑦𝑗𝑥1
𝑗+1
; ⁡1 ≤ 𝑗 ≤ 𝑚 − 1} ∪ {𝑦𝑚𝑥𝑛

𝑚}. The cardinality of vertex set and edge 

set, respectively are |𝑉(𝑎𝑚𝑎𝑙(𝐹𝑛,𝑣 = 𝑦,𝑚))|⁡= nm⁡ + ⁡1 and |𝐸(𝑎𝑚𝑎𝑙(𝐹𝑛,𝑣 = 𝑦,𝑚))| =

𝑚(2𝑛 − 1). 
  

If we show that 𝑑𝑖𝑚(𝑎𝑚𝑎𝑙(𝐹𝑛,𝑣 = 𝑦,𝑚)) =
𝑛𝑚

2
− 1 for𝑛 ≥ 7 and 𝑛 is even, then we 

will show the best lower bound namely 𝑑𝑖𝑚(𝑎𝑚𝑎𝑙(𝐹𝑛,𝑣 = 𝑦,𝑚)) ≥
𝑛𝑚

2
− 1. Assume that 

𝑑𝑖𝑚(𝑎𝑚𝑎𝑙(𝐹𝑛,𝑣 = 𝑦,𝑚)) <
𝑛𝑚

2
− 1.⁡This can be shown with take resolving set 𝑊 =

{𝑥1
1,𝑥4

1,𝑥1
2,𝑥4

2,𝑥6
2,𝑥1

3,𝑥4
3,𝑥6

3,𝑥1
4,𝑥4

4} so that it obtained the representation of the vertices 

𝑦 ∈ 𝑉(𝑎𝑚𝑎𝑙(𝐹6,𝑣 = 𝑦,4)) and 𝑥𝑖
𝑗
∈ 𝑉(𝑎𝑚𝑎𝑙(𝐹𝑛,𝑣 = 6,4)) respect to 𝑊. It can be seen 

that there is at least two vertices in 𝑎𝑚𝑎𝑙(𝐹6,𝑣 = 𝑦,4) which have the same 
representation respect to 𝑊, one of them is 𝑟(𝑥6

1|𝑊)⁡= (2,2,2,2,2,2,2,2,2,2) and 
𝑟(𝑥6

4|𝑊)⁡= (2,2,2,2,2,2,2,2,2,2) such that we have the cardinality of resolving set of 

𝑑𝑖𝑚(𝑎𝑚𝑎𝑙(𝐹𝑛,𝑣 = 𝑦,𝑚)) ≥
𝑛𝑚

2
− 1. 

Furthermore, we will prove that 𝑑𝑖𝑚(𝑎𝑚𝑎𝑙(𝐹𝑛,𝑣 = 𝑦,𝑚)) ≤
𝑛𝑚

2
− 1 with 

determine the resolving set 𝑊 = {𝑥𝑖
𝑗
; ⁡4 ≤ 𝑖 ≤ 𝑛; ⁡2 ≤ 𝑗 ≤ 𝑚;⁡𝑖 = 𝑜𝑑𝑑} − {𝑥𝑛

𝑚} ∪ {𝑥1
𝑗
; ⁡1 ≤

𝑗 ≤ 𝑚}. So, we have the cardinality of resolving set of 𝑎𝑚𝑎𝑙(𝐹𝑛,𝑣 = 𝑦,𝑚) namely |𝑊| =

⁡|{𝑥𝑖
𝑗
; ⁡4 ≤ 𝑖 ≤ 𝑛; ⁡1 ≤ 𝑗 ≤ 𝑚;𝑖⁡is⁡even} − {𝑥𝑛

𝑚} ∪ {𝑥1
𝑗
;1 ≤ 𝑗 ≤ 𝑚}| = (

𝑛−2

2
)𝑚⁡ + 𝑚 − 1 =

(
𝑛𝑚

2
− 1). The representation of the vertices 𝑦 ∈ 𝐹𝑛 and 𝑥 ∈ 𝐹𝑛 respect to 𝑊′ as follows. 

𝑟(𝑥𝑖
𝑗
|𝑊) = {(𝑎𝑖𝑘

𝑗
); ⁡1 ≤ 𝑖 ≤ 𝑛,1 ≤ 𝑗 ≤ 𝑚,1 ≤ 𝑘 ≤

𝑛𝑚

2
− 1}, where 

𝑎𝑖𝑘 =

{
 
 

 
 0;𝑓𝑜𝑟⁡𝑘 = 1,𝑘 = 2𝑖,2 ≤ 𝑖 ≤ (⌊

𝑛

2
⌋) ,1 ≤ 𝑗 ≤ 𝑚⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡

1;𝑓𝑜𝑟⁡𝑘 =
𝑖+1

2
,3 ≤ 𝑖 ≤ 𝑛,𝑖 ∈ 𝑜𝑑𝑑,1 ≤ 𝑗 ≤ 𝑚⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡

𝑘 =
𝑖−1

2
,5 ≤ 𝑖 ≤ 𝑛,𝑖 ∈ 𝑜𝑑𝑑,1 ≤ 𝑗 ≤ 𝑚⁡𝑎𝑛𝑑⁡(𝑘 ≠ 𝑚 ∩ 𝑖 ≠ 𝑛)

2;𝑓𝑜𝑟⁡1 ≤ 𝑗 ≤ 𝑚,𝑘,𝑖 = 𝑜𝑡ℎ𝑒𝑟𝑠⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡

 

 𝑟(𝑦|𝑊) = {(𝑎𝑖𝑘); ⁡1 ≤ 𝑖 ≤ 𝑛,1 ≤ 𝑘 ≤
𝑛−2

2
}, where 

𝑎𝑖𝑘 = {1;𝑓𝑜𝑟⁡1 ≤ 𝑘 ≤
𝑛𝑚−𝑛

2
, 𝑖 = 1 

 
It can be seen that every vertex in 𝑎𝑚𝑎𝑙(𝐹6,𝑣,4) have distinct representation 

respect to 𝑊, such that the cardinality of resolvng set in 𝑎𝑚𝑎𝑙(𝐹𝑛,𝑣,𝑚) is 
𝑛𝑚

2
− 1 or 

𝑑𝑖𝑚(𝑎𝑚𝑎𝑙(𝐹𝑛,𝑣,𝑚)) ≤
𝑛𝑚

2
− 1. Thus, we conclude that 𝑑𝑖𝑚(𝑎𝑚𝑎𝑙(𝐹𝑛,𝑣,𝑚)) =⁡

𝑛𝑚

2
− 1.

 ∎ 



On the Metric Dimension of Some Operation Graphs 

Marsidi 93 

 
Fig 3. The Metric Dimension of Amalgamation of Fan Graph A𝑚𝑎𝑙(𝐹6,𝑣 = 𝑦,3). 

 
Theorem 2.4. For 𝑚 ≥ 2, the metric dimension of 𝑠ℎ𝑎𝑐𝑘(𝐻2

2,𝑒,𝑚) is 

𝑑𝑖𝑚(𝑠ℎ𝑎𝑐𝑘(𝐻2
2,𝑒,𝑚)) = 2. 

Proof. The shackle of fan graph, denoted by 𝑠ℎ𝑎𝑐𝑘(𝐻2
2,𝑒,𝑚)is a connected graph with 

vertex set 𝑉(𝑠ℎ𝑎𝑐𝑘(𝐻2
2,𝑒,𝑚)) = {𝑥𝑗; ⁡1 ≤ 𝑗 ≤ 𝑚 + 1} ∪ {𝑦𝑗; ⁡1 ≤ 𝑗 ≤ 𝑚 + 1} and edge set 

𝐸(𝑠ℎ𝑎𝑐𝑘(𝐻2
2,𝑒,𝑚)) = {𝑥𝑗𝑦𝑗; ⁡1 ≤ 𝑗 ≤ 𝑚 + 1} ∪ {𝑥𝑗𝑦𝑗+1; ⁡1 ≤ 𝑗 ≤ 𝑛} ∪ {𝑥𝑗+1𝑦𝑗; ⁡1 ≤ 𝑗 ≤

𝑚}. The cardinality of vertex set and edge set, respectively are |𝑉(𝑠ℎ𝑎𝑐𝑘(𝐻2
2,𝑒,𝑚))| =

⁡2𝑚 + 2 and |𝐸(𝑠ℎ𝑎𝑐𝑘(𝐻2
2,𝑒,𝑚))| = 3𝑚 + 1. 

 The proof that the lower bound of 𝑠ℎ𝑎𝑐𝑘(𝐻2
2,𝑒,𝑚) is 𝑑𝑖𝑚(𝑠ℎ𝑎𝑐𝑘(𝐻2

2,𝑒,𝑚)) ≥ 2. 
Based on Proposition 1, that 𝑑𝑖𝑚(𝐺) = 1 if only if 𝐺 ≅ 𝑃𝑛. The graph 𝑠ℎ𝑎𝑐𝑘(𝐻2

2,𝑒,𝑚) does 
not isomorphic to path 𝑃𝑛 such that 𝑑𝑖𝑚(𝑠ℎ𝑎𝑐𝑘(𝐻2

2,𝑒,𝑚)) ≥ 2. Furthermore, we proof 
that the upper bound of 𝑠ℎ𝑎𝑐𝑘(𝐻2

2,𝑒,𝑚) is 𝑑𝑖𝑚(𝑠ℎ𝑎𝑐𝑘(𝐻2
2,𝑒,𝑚)) ≤ 2, we choose the 

resolving set 𝑊 = {𝑥1,𝑦1}. 
The representation of the vertices 𝑣 ∈ 𝑉(𝑠ℎ𝑎𝑐𝑘(𝐻2

2,𝑒,𝑚)) respect to 𝑊 as follows. 
 

𝑟(𝑥𝑗|𝑊) =⁡(𝑗 − 1,𝑗);𝑗 ∈ 𝑜𝑑𝑑 𝑟(𝑦𝑗|𝑊) =⁡(𝑗, 𝑗 − 1);𝑗 ∈ 𝑜𝑑𝑑 

𝑟(𝑥𝑗|𝑊) =⁡(𝑗, 𝑗 − 1);𝑗 ∈ 𝑒𝑣𝑒𝑛 𝑟(𝑦𝑗|𝑊) =⁡(𝑗 − 1,𝑗);𝑗 ∈ 𝑒𝑣𝑒𝑛 

 
Vertex 𝑣 ∈ 𝑉(𝑠ℎ𝑎𝑐𝑘(𝐻2

2,𝑒,𝑚)) are distict. So, we have the cardinality of resolving 
set 𝑊 is |𝑊| = 2. Thus, the upper bound of 𝑠ℎ𝑎𝑐𝑘(𝐻2

2,𝑒,𝑚) is 𝑑𝑖𝑚(𝑠ℎ𝑎𝑐𝑘(𝐻2
2,𝑒,𝑚)) ≤ 2. 

It concludes that 𝑑𝑖𝑚(𝑠ℎ𝑎𝑐𝑘(𝐻2
2,𝑒,𝑚)) = 2. 

 ∎ 



On the Metric Dimension of Some Operation Graphs 

Marsidi 94 

 
Fig 4. The Metric Dimension of Sℎ𝑎𝑐𝑘(𝐻2

2,𝑒,3). 
 

CONCLUSIONS 

In this paper, the result show that the local metric dimension of some graph operation 
such as joint graph 𝑃𝑛 + 𝐶𝑚, amalgamation of parachute, amalgamation of fan, and 
𝑠ℎ𝑎𝑐𝑘(𝐻2

2,𝑒,𝑚). 
 

ACKNOWLEDGMENTS  

We gratefully acknowledge the support from DRPM KEMENRISTEKDIKTI 2018 indonesia. 
 

REFERENCES 

 

[1]  G. Chartrand, E. Salehi, and P. Zhang, "The partition dimension of a graph," 
Aequationes Math., vol. 59, pp. 45-54, 2000. 

[2]  G. Chartrand, L. Eroh, and M. A. Johnson, " Resolvability in graphs and the metric 
dimension of a graph," Discrate Appl. Math., vol. 105, pp. 99-113, 2000. 

[3]  Marsidi, Dafik, I. H. Agustin, and R. Alfarisi, “On the local metric dimension of line 
graph of special graph,” CAUCHY, vol. 4, no. 3, pp. 125-130, 2016.  

[4]  I. G. Yero, D. Kuziak, and J. S. Rodríguez-Velázquez, “On the metric dimension of 
corona product graphs,” Computers and Mathematics with Applications, vol. 61, pp. 
2793-2798, 2011.  

[5]  H. Fernau, P. Heggernes, P. Hof, D. Meister, and R. Saei, “Computing the metric 
dimension for chain graphs,” Information Processing Letters, vol. 115, pp. 671-676, 
2015. 

[6]  J. Cáceres, C. Hernando, M. Mora, I. M. Pelayo, and M. L. Puertas, “On the metric 
dimension of infinite graphs,” Discrete Applied Mathematics, vol. 160, pp. 2618-2626, 
2012. 

[7] M. Fehr, S. Gosselin, and O. R. Oellermann, “The metric dimension of cayley digraphs,” 
Discrete Mathematics, vol. 360, pp. 31-41, 2006. 

[8] T. K. Maryati, A. N. M. Salman, and E. T. Baskoro, “On H-supermagic labelings for 
certain shackles and amalgamations of a connected graph,” Utilitas Mathematica, 
2010. 

[9] I. H. Agustin, Dafik, S. Latifah, and R. M. Prihandini, “A super (A,D)-Bm-antimagic total 
covering of a generalized amalgamation of fan graphs,” CAUCHY, vol. 4, no. 4, pp. 146-
154, 2017.