The Metric Dimension and Local Metric Dimension of Relative Prime Graph


CAUCHY –Jurnal Matematika Murni dan Aplikasi 
Volume 6(3) (2020), Pages 149-161 
p-ISSN: 2086-0382; e-ISSN: 2477-3344 

Submitted: August 06, 2020 Reviewed: October 07, 2020 Accepted: 10 November 2020 
DOI: http://dx.doi.org/10.18860/ca.v6i3.10103  

The Metric Dimension and Local Metric Dimension of Relative Prime 
Graph 

Inna Kuswandari1, Fatmawati2, Mohammad Imam Utoyo3  

Mathematics Department, Faculty of Science and Technology, Universitas Airlangga, 
Mulyorejo, Surabaya 60115, Indonesia.  

 

Email: ikuswandari94@gmail.com, fatma47unair@gmail.com, m.i.utoyo@fst.unair.ac.id 

ABSTRACT  

This study aims to determine the metric dimensions and local metric dimensions of relative prime 
graphs formed from modulo 𝑛 integer rings, namely 𝐺ℤ𝑛 with 𝑛 ≥ 2. As a vertex set is ℤ𝑛 ∖{0} 

and 𝑢𝑣 ∈ 𝐺ℤ𝑛 if 𝑢 and 𝑣 are relatively prime. By finding the pattern elements of resolving set and local 

resolving set, it can be shown the value of the metric dimension and the local metric dimension of 
𝐺ℤ𝑛 are 𝑛 − 2+ 𝑘 and |𝑃0|− 1+ 𝑘 respectively, where 𝑘 is the number of vertices groups that formed 

multiple 2,3, … , 𝑘 and |𝑃0| is the cardinality of set 𝑃0. This research can be developed by determining 
the fractional metric dimension, local fractional metric dimension and studying the advanced 
properties of graphs related to their forming rings.  

Key Words : Metric Dimension; Modulo 𝑛; Relative Prime Graph; Resolving Set; Rings. 

INTRODUCTION 

Graph 𝐺 is defined as a non-empty and finite set of 𝑉(𝐺) whose elements are called 
vertices and set 𝐸(𝐺) (maybe empty) whose elements are called edges which are the 
unordered pair of different vertices in 𝑉(𝐺) [1]. Any problems whose objects can be 
described as vertices and edges can be solved by the concept of graph theory, this has 
become one of the supporting factors in the field of graph theory research developing very 
rapidly today. 

The notion of metric dimensions was introduced firstly by [2] and independently by 
[3] (in [4]). In [3], the concepts of bases and dimensions have been built on the graph. A 
bases on a graph is a set of vertices with minimal cardinality that implies in each vertex of 
graph having a different representation (resolving set) to the bases, while the dimensions 
are number elements of the bases. Meanwhile, the local metric dimension was introduced 
by [5] by considering different representations of two adjacent vertices so that the local 
metric dimension of a graph is obtained. The research related to the metric dimensions and 
local metric dimensions of a graph has been carried out by many researchers no exception 
to the graph of the results of operations (comb, corona, joint, etc.). 

The development of research in the field of graph theory is also supported by the 
expansion of research objects in algebraic systems, namely groups or rings. In [6], the zero 
divisor graph is introduced from any commutative ring by defining the vertices on the graph 
are elements of the ring, while the two vertices are adjacent if the product is zero.  By using 

http://dx.doi.org/10.18860/ca.v6i3.10103
mailto:ikuswandari94@gmail.com
mailto:fatma47unair@gmail.com
mailto:utoyo@fst.unair.ac.id


The Metric Dimension and Local Metric Dimension of Relative Prime Graph  
 

Fatmawati  150 

the definition in [6], the research was also carried out in [7,8,9] and succeeded in finding 
several properties related to the diameter, girth, isomorphism of the graph, radius, and 
domination set of zero divisor graphs constructed from the commutative and non- 
commutative rings. In addition to the zero divisor of graph, research has also been developed 
on the Jacobson graph formed from commutative rings that have nonzero unit elements 
[10,11]. The definition of vertices and edges is built from the radical Jacobson and the unit 
of the ring. Specifically, in [11], Jacobson graph was formed from the commutative ring 𝑍3𝑛  
and obtained several properties that related to the graph with its forming ring. 

Some of the research above inspired the author to examine the metric dimensions and 
local metric dimensions on graphs constructed from commutative rings. As an object of 
research, we choose a ring of modulo 𝑛 integer with the adjacency between two vertices was 
chosen based on the relative prime properties between the two vertices. The following is 
given the definition of the greatest common divisor and the relative prime of two positive 
integers. 

 
Definition 1 [12]. Let 𝑎 and 𝑏 be two positive integers. The positive integer 𝑑 that satisfies 

𝑑 = 𝑝𝑎 + 𝑞𝑏 for some integer 𝑝 and 𝑞 is called greatest common divisor (abbreviated 
gcd) of 𝑎 and 𝑏, denoted by 𝑑 = gcd (𝑎,𝑏). 

 
Definition 2 [12]. Two positive integers 𝑎 and 𝑏 are relatively prime if gcd(𝑎,𝑏) = 1. 
 

The purpose of this study is to determine the metric dimensions and local metric 
dimensions of relative prime graphs. The definition of metric dimensions and local metric 
dimensions which refer to [13] and [5] is given as follows. 
 
Definition 3 [13]. Suppose that 𝐺 is a connected graph of order 𝑛 and 𝑊 = {𝑤1,𝑤2,…,𝑤𝑗} ⊆

𝑉(𝐺),1 ≤ 𝑗 ≤ 𝑛 is an ordered set of  j-tuples of vertices in 𝐺. Representation of vertice 
𝑣 ∈ 𝑉(𝐺) with respect to 𝑊 is an ordered pair j-tuples 𝑟(𝑣|𝑊) =
(𝑑(𝑣,𝑤1),𝑑(𝑣,𝑤2),…,𝑑(𝑣,𝑤𝑗)), where 𝑑(𝑣,𝑤𝑖) representing the distance between 

vertex 𝑣 and vertex 𝑤𝑖,   1 ≤ 𝑖 ≤ 𝑗. The set 𝑊 is called the resolving set of 𝐺 if each 

vertex in 𝐺 has different representation with respect to 𝑊. The resolving set with a 
minimum cardinality is called a bases, whereas number of elements on the bases are 
called dimensions of the graph 𝐺, denoted by 𝑑𝑖𝑚(𝐺). Since the calculation of 
dimensions in a graph is built using the concept of distance (metric), it is called the 
metric dimension. 

 
Definition 4 [5]. Let G be the connected graph and 𝑊 ⊆ 𝑉(𝐺). The set 𝑊 is called the local 

resolving set of a graph 𝐺 if each of two adjacent vertices in 𝐺 has a different 
representation with respect to 𝑊, i.e. 𝑢𝑣 ∈ 𝐸(𝐺) implies 𝑟(𝑢|𝑊) ≠ 𝑟(𝑣|𝑊). The set of 
local resolving set with minimal cardinality is called a local bases, while number of 
elements on a bases are called the local metric dimensions of graph 𝐺, denoted by 
𝑑𝑖𝑚𝑙(𝐺). 

 

METHODS  

This study aims to determine the metric dimensions and local metric dimensions of 
relative prime graph 𝐺𝑍𝑛. The most important step in determining the metric dimensions 

and local metric dimensions is to determine the pattern of resolving set and local resolving 
set that have a minimum cardinality as a bases set. The main difference between them is that 



The Metric Dimension and Local Metric Dimension of Relative Prime Graph  
 

Fatmawati  151 

1 

1 1 

2 

3 

2 

3 3 4 4 5 

2 

6 

2 

on the local metric dimension the different representation are only required at adjacent 
vertices. 

 

RESULTS AND DISCUSSION 

In this section, we will discuss the definition of a relative prime graph built from a ring 
of modulo 𝑛 integer and an exploration of the basic properties of a relative prime graph 
related to the characteristics of a graph. The discussion begins with the definition of a 
relative prime graph. 

 
Definition 5. Let ℤ𝑛 be a rings of modulo 𝑛 integer ℤ𝑛, where 𝑛 positive integer and 𝑛 ≠ 1. 

We defined a new graph 𝐺 with 𝑉(𝐺) = ℤ𝑛 ∖{0} and 𝐸(𝐺) = {𝑢𝑣;𝑢 relatively prime 
with 𝑣}. Graph 𝐺 which formed from ring of modulo 𝑛 integer with add relatively prime 
as condition for adjacency two vertices are called relative prime graph, denoted by 𝐺ℤ𝑛. 

The number of vertices of 𝐺𝑍𝑛is denoted |𝑉(𝐺ℤ𝑛)| and the number of edges is denoted 

|𝐸(𝐺ℤ𝑛)|. 

 
Example: 

     

          

 

                              A           B      C 

Figure 1. Some relative prime graphs 
 A: 𝐺ℤ4;  B: 𝐺ℤ5;   C: 𝐺ℤ7 

 
The graph on Figure 1:  
A: 𝐺ℤ4 consists of three vertices, namely 1,2,3 which are mutually relative prime. Hence 

vertex 1 adjacent to 2, vertex 2 adjacent to 3, and vertex 3 adjacent to 1.  
B: 𝐺ℤ5 consists of four vertices, namely 1,2,3,4. The adjacency of vertices 1,2,3 similar with 

condition of 𝐺ℤ4. Furthermore, vertex 4 is relatively prime to 1 and 3, while vertex 2 is not  

relatively prime to 4. Hence vertex 2 is not adjacent to 4. 
C: 𝐺ℤ7 consists of six vertices, namely 1,2,3,4,5,6. Vertex 1 is relatively prime to vertices 

2,3,4,5,6; vertex 2 is relatively prime to vertices 1,3,5; vertex 3 is relatively prime to 
vertices 1,2,4,5; vertex 4 is relatively prime to vertices 1,3,5; vertex 5 is relatively prime 
to vertices 1,2,3,4,6; and vertex 6 is relatively prime to vertices 1,3,5. Since the three 
vertices (i.e. 2,4,6) are not relatively prime to each other, then they are not adjacent to 
each other. Likewise, vertex 3 is not adjacent to 6 because 3 is not relatively prime to 6.  

 
The results of this study begin with an exploration the basic properties of 𝐺ℤ𝑛, 

furthermore determine the metric dimensions and local metric dimensions of 𝐺ℤ𝑛. Based on 

Definition 5 above, there are some basic properties of 𝐺ℤ𝑛 for 𝑛 ≥ 2,  as follows: 

a. The set of vertices in 𝐺ℤ𝑛is  𝑉(𝐺ℤ𝑛) = {1,2,3,…,𝑛 − 1}, hence |𝐸(𝐺ℤ𝑛)| = 𝑛 − 1. 

b. 𝐺ℤ𝑛 is not an empty graph. 

c. 𝐺ℤ𝑛 is a trivial graph for 𝑛 = 2 because it consist only one vertex.  



The Metric Dimension and Local Metric Dimension of Relative Prime Graph  
 

Fatmawati  152 

d. 𝐺ℤ𝑛 is a connected graph. 

e. 𝐺ℤ𝑛 is a complete graph for 𝑛 = 2,3,4. Specifically for 𝑛 = 3  it is a path graph and for 𝑛 =

4  it is a sikel graph.  
f. 𝐺ℤ𝑛 is a regular graph for 𝑛 = 3,4 because every vertex has the same degree. 

g. There is a vertex 1 that adjacent to every vertex in 𝐺ℤ𝑛 for 𝑛 ≥ 3.  

Based on Definition 5, a vertex 𝑢 is adjacent to vertex 𝑣 if 𝑢 is relatively prime with 𝑣. 
In 𝐺ℤ𝑛, there are vertices that are adjacent to each vertex in 𝐺ℤ𝑛, included in this category are 

vertex 1 and several vertices which are prime numbers. Based on the definition of two 
adjacent vertices on 𝐺ℤ𝑛, the adjacency of vertices are divided into two groups, namely (1) 

vertices that are adjacent to every vertex, and (2) vertices that are not adjacent to each other. 
The vertices that not adjacent are the vertices that not relatively prime to each other, i.e. the 
vertices that have a common divisor other than 1. Furthermore, the vertices that have a 
common divisor other than 1 can be divided into multiple of 2, multiple of 3, multiple of 5, 
..., multiple of 7, ... . Suppose 𝐴 = {2,3,5,7,…} = {𝑝1,𝑝2,…,𝑝𝑘} represent a set of ordered 
prime numbers, then the non adjacent vertices are grouped together in multiples of 2, 
multiples of 3, ... to multiples of prime numbers 𝑝𝑘, where 2𝑝𝑘 ≤ 𝑛 − 1. In this case, 𝑝𝑘 is the 
largest prime numbers and 𝑘 represents number of groups (multiples 2, multiples 3, etc.). 
The vertices that adjacent to every vertices in 𝐺ℤ𝑛 are categorized into group 𝑝0. 

Example: in 𝐺ℤ15, 𝑉(𝐺ℤ15) = {1,2,3,…, 14}. The grouping of vertices in 𝐺ℤ15 are: 

The vertices in group 𝑝0 are 1,11,13. 
The vertices in group of multiple 𝑝1= 2 are 2,4,6,8,10,12,14. 
The vertices in group of multiple 𝑝2= 3 are 3,6,9,12. 
The vertices in group of multiple 𝑝3= 5 are 5,10. 
The vertices in group of multiple 𝑝4= 7 are 7,14. 
In this case, there are four groups of multiples, where 7 is the largest prime number that 
satisfy 2x7 ≤ 14. The vertices 1,11,13 are adjacent to every vertex in 𝐺ℤ15 so that it is 

categorized in group 𝑝0. It appears that there are vertices that are in more than one group of 
multiples, for example vertices 6 and 12 are in groups of multiple 2 and multiple 3. Likewise, 
vertex 15 is in groups of multiple 3 and multiple 5. Furthermore, if 𝑃𝑖 is the set of vertices in 
the group of multiples 𝑝𝑖, where 𝑖 = 1,2,…,𝑘 and ⌊𝑥⌋ represent the largest  integer that same 

or less than 𝑥, then |𝑃𝑖| = ⌊
𝑛−1

𝑝𝑖
⌋. On 𝐺ℤ15, |𝑃1| = ⌊

14

2
⌋ = 7; |𝑃2| = ⌊

14

3
⌋ = ⌊4,67⌋ = 4; |𝑃3| =

⌊
14

5
⌋ = ⌊2,8⌋ = 2; |𝑃4| = ⌊

14

7
⌋ = 2.  So, in general in 𝐺ℤ𝑛 the number of vertices in the group of 

multiples 𝑝𝑖 is ⌊
𝑛−1

𝑝𝑖
⌋, while the number of vertices in the group of multiples 𝑝𝑖 and 𝑝𝑗 is  ⌊

𝑛−1

𝑝𝑖.𝑝𝑗
⌋ 

where 1 ≤ 𝑖,𝑗 ≤ 𝑘. The lemma that expressed the number of edge of 𝐺ℤ𝑛 is given as follows.  

 

Lemma 1. |𝐸(𝐺ℤ𝑛)| =
(𝑛−1)(𝑛−2)

2
− ∑ (

⌊
𝑛−1

𝑝𝑖
⌋

2
)𝑘𝑖=1 , where ⌊

𝑛−1

𝑝𝑖
⌋ is the number of vertices in 

groups of multiples 𝑝𝑖, 𝑖 = 1,2,…,𝑘 and 2𝑝𝑘 ≤ 𝑛 − 1. 
Proof. As explained above, the vertices on 𝐺ℤ𝑛 are divided into 2 major groups, namely the 

group 𝑝0 and the groups of multiples 𝑝𝑖. Due to the specific properties of each group, the 
number of edges on graph 𝐺ℤ𝑛 can be calculated by asumption the number of edges of the 

complete graph with 𝑛 −1 vertices, then edge reduction is done based on the non relatively 
prime properties between any two vertices.  As we know, the number of edge of the complete 

graph with 𝑛 − 1 vertices is  
(𝑛−1)(𝑛−2)

2
. Since an edge is formed by two different vertices, 



The Metric Dimension and Local Metric Dimension of Relative Prime Graph  
 

Fatmawati  153 

then there is a reduction in the edge for each group of multiples 𝑝𝑖 as many as (
⌊
𝑛−1

𝑝𝑖
⌋

2
).  Thus, 

|𝐸(𝐺ℤ𝑛)| =
(𝑛−1)(𝑛−2)

2
− ∑ (

⌊
𝑛−1

𝑝𝑖
⌋

2
)𝑘𝑖=1          

 
         Table 1. Number of edges on graph 𝐺ℤ𝑛 

𝑛 |𝑉(𝐺ℤ𝑛)| 
Groups of 
vertices 

Reduction of edge  |𝐸(𝐺ℤ𝑛)| 

2 1 - - 0 

3 2 𝑝0 : 1,2 - 2(2− 1)

2
= 1 

4 3 𝑝0 : 1,2,3 - 3(3− 1)

2
= 3 

5 4 𝑝0 : 1,3 - 4(4− 1)

2
− 1 = 5 

𝑝1 : 2,4 (
2
2
) = 1 

6 5 𝑝0 : 1,3,5 - 5(5− 1)

2
− 1 =  9 

𝑝1 : 2,4 (
2
2
) = 1 

7 6 𝑝0 : 1,5 - 6(6−1)

2
−3 −1 =  11 

𝑝1 : 2,4,6 (
3
2
) = 3 

𝑝2 : 3,6 (
2
2
) = 1 

8 7 𝑝0 : 1,5,7 - 7(7−1)

2
−3 −1 =  17 

𝑝1 : 2,4,6 (
3
2
) = 3 

𝑝2 : 3,6 (
2
2
) = 1 

9 8 𝑝0 : 1,5,7 - 8(8−1)

2
−6 −1 =  21 

𝑝1 : 2,4,6,8 (
4
2
) = 6 

𝑝2 : 3,6 (
2
2
) = 1 

 
The degree of each vertex on any graph is the number of the vertices that adjacent to 

that vertex. Thus, the degree of vertex 𝑢 ∈ 𝑉(𝐺ℤ𝑛) is determined based on their adjacency to 

(𝑛 − 2) other vertices as in Observation 2. Furthermore, Lemma 3 states the minimum and 
maximum degree of the vertex on 𝐺ℤ𝑛. 

 
Observation 2. If deg𝐺ℤ𝑛

(𝑢) denoted the degree of any vertex 𝑢 ∈ 𝑉(𝐺ℤ𝑛), then 

deg𝐺ℤ𝑛
(𝑢) = |{𝑣 ∈ 𝑉(𝐺ℤ𝑛):𝑣 relatively prime with 𝑢}|.  

 

Lemma 3. If  𝑢 ∈ 𝑉(𝐺ℤ𝑛), then  deg𝐺ℤ𝑛
(𝑢) = {

    0,    
1,

2 ≤ deg𝐺ℤ𝑛
(𝑢) ≤ 𝑛 − 2,   

𝑛 = 2
𝑛 = 3
𝑛 ≥ 4

 

Proof. Let 𝑢 ∈ 𝑉(𝐺ℤ𝑛).  



The Metric Dimension and Local Metric Dimension of Relative Prime Graph  
 

Fatmawati  154 

- For 𝑛 = 2, then 𝑢 = 1 and 𝐺ℤ𝑛 is the trivial graph, hence deg𝐺ℤ𝑛
(𝑢) = 0. 

- For 𝑛 = 3, then 𝑢 ∈ {1,2}. The number 1 is relatively prime with 2, hence vertex 1 
adjacent to vertex 2. Thus, deg𝐺ℤ𝑛

(𝑢) = 1.  

- For 𝑛 ≥ 4, it means |𝑉(𝐺ℤ𝑛)| ≥ 3. 

To show the minimum degree of any vertex is 2, we use Claim: every vertex in 𝐺ℤ𝑛 is 

adjacent to at least two other vertices. 
Proof of Claim: Since the criterion for two adjacency vertices are relative prime and the 
vertices in 𝐺ℤ𝑛 are natural numbers, it is sufficient to show that any natural number 

other than 1 must be relative prime to the natural number before and after it. Suppose 
any natural number 𝑎 where  𝑎 ≠ 1, it will be shown that 𝑎 relative prime with 𝑎 − 1 
and 𝑎 also relative prime with 𝑎 + 1.  Based on Definition 2, the natural number 𝑎 is 
relative prime with 𝑎 − 1 if there are integers 𝑝 and 𝑞 such that 1 = 𝑝𝑎 + 𝑞(𝑎 − 1). By 
choosing 𝑝 = 1 and 𝑞 = −1, equality hold. Hence 𝑎 relative prime with 𝑎 − 1. In a 
similar way, it can be shown that 𝑎 relative prime with 𝑎 + 1. Thus, 𝑎 adjacent to 𝑎 − 1 
and also 𝑎 adjacent to 𝑎 + 1. Therefore, for any 𝑢 ∈ 𝑉(𝐺ℤ𝑛),  there are at least two 

vertices that adjacent to 𝑢, so deg𝐺ℤ𝑛
(𝑢) ≥ 2. On the other hand, based on the property 

of the group 𝑝0, where each vertex is adjacent to every vertex in 𝐺ℤ𝑛, so for any 𝑢 ∈ 𝑃0, 

deg𝐺ℤ𝑛
(𝑢) = |𝑉(𝐺ℤ𝑛)|− 1 = 𝑛 − 1 − 1 = 𝑛 −2 and this is the maximum degree of any 

vertex in 𝐺ℤ𝑛. Thus, it is proven that 2 ≤ deg𝐺ℤ𝑛
(𝑢) ≤ 𝑛 − 2, for 𝑛 ≥ 4 and the whole 

lemma is proven.         
 

For example, on graph 𝐺ℤ7 we have 𝑉(𝐺ℤ7) = {1,2,3,4,5,6}. The degree of each vertex is:         

deg𝐺ℤ7
(1) = |{2,3,4,5,6}| = 5;  deg𝐺ℤ7

(2) = |{1,3,5}| = 3;  deg𝐺ℤ7
(3) = |{1,2,4,5}| = 4;  

deg𝐺ℤ7
(4) = |{1,3,5}| = 3; deg𝐺ℤ7

(5) = |{1,2,3,4,6}| = 5;  deg𝐺ℤ7
(6) = |{1,5}| = 2. It can be 

seen that 2 ≤ deg𝐺ℤ7
(𝑢) ≤ 5,  for every 𝑢 ∈ 𝑉(𝐺ℤ7). 

In 𝐺ℤ𝑛, there is vertex 1 which is adjacent to each vertex in 𝐺ℤ𝑛. Several other vertices are 

also similar. Vertices of this property will form a complete subgraph of 𝐺ℤ𝑛 as shown in 

Theorem 4. 
 
Theorem 4. There is a complete subgraph formed by vertices of 𝐺ℤ𝑛. 

Proof. A complete graph is a graph where every two vertices are adjacent. Based on the 
property of the vertices on 𝐺ℤ𝑛, there are vertices that are adjacent to each vertex, namely 

the vertices in the group 𝑝0. These vertices will form the complete subgraph 𝐾𝑚, where  
𝑚 = |{𝑢 ∈ 𝑉(𝐺ℤ𝑛):gcd(𝑢,𝑣) = 1,∀𝑣 ∈ 𝑉(𝐺ℤ𝑛)}|.         

 
From Theorem 4, the vertices in 𝐺ℤ𝑛 that form the complete subgraph are vertices in 

group 𝑝0, where 𝑚 = |{𝑢 ∈ 𝑉(𝐺ℤ𝑛):gcd(𝑢,𝑣) = 1,∀𝑣 ∈ 𝑉(𝐺ℤ𝑛)}| = |𝑃0|. On the other hand, 

the vertices in the group of multiples 𝑝𝑖, 𝑖 = 1,2,…,𝑘 have the same property that they are 
not adjacent to each other. This inspires that the vertices in the group of multiples 𝑝𝑖, 𝑖 =
1,2,…,𝑘 form the multipartite subgraph of 𝐺ℤ𝑛 which is stated in the Theorem 5. 

 
Theorem 5. For 𝑛 ≥ 5, 𝐺ℤ𝑛 is isomorphic with a 𝐾𝑚 + 𝐻 graph where 𝐻 is the 𝑘-partite 

graph, 𝐾𝑚 is a complete graph with 𝑚 vertices and 𝑚 = |𝑃0|.  
Proof. Based on Theorem 4, the vertices in the group 𝑝0 form the complete subgraph 𝐾𝑚 of 
𝐺ℤ𝑛. Meanwhile, the vertices in the group of multiples 𝑝𝑖, 𝑖 = 1,2,…,𝑘 are not adjacent to 



The Metric Dimension and Local Metric Dimension of Relative Prime Graph  
 

Fatmawati  155 

each other for each 𝑖, so the vertices in the group of multiples 𝑝𝑖 can be partitioned into 𝑘 
partitions with each partition consisting of vertices in the same group of multiples. On the 
same partition, there are no adjacent vertices according to the properties of the vertices in 
the group of multiples 𝑝𝑖. The connectedness of the vertices between partitions is based on 
the relatively prime properties of these vertices. Since every vertex in 𝐾𝑚 is adjacent to every 
vertex in the group of multiples 𝑝𝑖, this means that every vertex in 𝐾𝑚 is adjacent to every 
vertex on all partitions (as many as 𝑘 partitions) that are formed. Suppose the 𝑘 partitions 
formed along with adjacency their vertices are called graph 𝐻, then 𝐻 is a 𝑘-partite graph 
formed from vertices in the group of multiples 𝑝𝑖. Every vertex in the group 𝑝0 is adjacent to 
every vertex in 𝐺ℤ𝑛, especially in the group of multiples 𝑝𝑖. This means that every vertex in 

𝐾𝑚 is adjacent to every vertex in 𝐻. Therefore, there is a bijective function 𝑓 from 𝑉(𝐺ℤ𝑛) to 

𝑉(𝐾𝑚 + 𝐻) which preserves the adjacency between vertices in 𝐺ℤ𝑛. Thus, 𝐺ℤ𝑛 ≅ 𝐾𝑚 + 𝐻.       

 
Theorem 5 applies for 𝑛 ≥ 5, spesifically for 𝑛 = 2,3,4 then 𝐺ℤ𝑛 ≅ 𝐾𝑛−1 (complete graph 

with 𝑛 −1 vertices). For example: on 𝐺ℤ8 where 𝑉(𝐺ℤ8) = {1,2,3,4,5,6,7}.  

 

             

  ≅  + 

 

                  𝐺ℤ8                                                      𝐾3     +   𝐻2,2 

Figure 2. Isomorphism 𝐺ℤ8 with 𝐾3 + 𝐻2,2 

 
Figure 2 illustrates the isomorphism 𝐺ℤ8 with 𝐾3 + 𝐻2,2 where 𝐻2,2 is 2-partite graph. 

In 𝐺ℤ8, vertices 1,5,7 is adjacent to each vertex such that 𝑚 = 3. Meanwhile, the vertices in 

the group  of multiples 2 are 2,4,6; the vertices in the group of multiples 3 are 3,6 and no 
vertex are multiples of 5, so there are 2 partitions. In the example above, the vertices on the 
first partition are 2 and 4, while the vertices on the second partition are 3 and 6. Since the 
number of vertices on the first partition is 2 and the number of vertices on the second 
partition is 2, it is written 𝐻2,2. The existence of graph 𝐻2,2 as a 2-partite graph is not unique. 

Another alternative is that if three vertices are selected on the first partition (i.e. vertices 
2,4,6) and on the second partition one vertex is chosen (i.e. vertex 3), then the 2-partite 
graph in this case is written 𝐻3,1.  Thus, 𝐺ℤ8 ≅ 𝐾3 + 𝐻2,2 ≅ 𝐾3 + 𝐻3,1.  

Next, we will be determined the value of the metric dimension and the local metric 
dimension of 𝐺ℤ𝑛 for 𝑛 ≥ 2. The determination of metric dimensions is calculated using the 

concept of the distance between two vertices, namely the length of the shortest path 
connecting the two vertices.  

 
Theorem 6. If 𝑢,𝑣 ∈ 𝑉(𝐺ℤ𝑛), then 𝑑(𝑢,𝑣) ≤ 2.  

Proof. Let 𝑢,𝑣 ∈ 𝑉(𝐺ℤ𝑛). Based on Theorem 5, there are three possibilities for 𝑢 and 𝑣, 

namely (i) 𝑢,𝑣 ∈ 𝑉(𝐾𝑚), (ii) 𝑢,𝑣 ∈ 𝑉(𝐻), dan (iii) 𝑢 ∈ 𝑉(𝐾𝑚) ,𝑣 ∈ 𝑉(𝐻). 
(i) Suppose 𝑢,𝑣 ∈ 𝑉(𝐾𝑚). Since 𝐾𝑚 is a complete graph, then distance between two 

different vertices is 1, so that  𝑑(𝑢,𝑣) = {
0,   𝑢 = 𝑣
1,   𝑢 ≠ 𝑣

 . 

1 2 

3 

5 

4 

7 

6 

1 

5 7 

3 2 

4 6 



The Metric Dimension and Local Metric Dimension of Relative Prime Graph  
 

Fatmawati  156 

(ii) Suppose 𝑢,𝑣 ∈ 𝑉(𝐻), there are two condition, i.e. 𝑢 and 𝑣 on the same partitions or  𝑢 
and 𝑣 on the different partitions.  
a. If 𝑢 and 𝑣 are vertex on the same partition, then there is 𝑧 ∈ 𝑉(𝐾𝑚) so that 𝑑(𝑢,𝑧) =

1 and 𝑑(𝑧,𝑣) = 1. Therefore, 𝑑(𝑢,𝑣) = 2. So 𝑑(𝑢,𝑣) = {
0,
2,
    𝑢 = 𝑣
   𝑢 ≠ 𝑣

. 

b. If 𝑢 and 𝑣 are vertices on the different partition, then the distance is 1 if 𝑢 adjacent 
to 𝑣. For vertex 𝑢 which is not adjacent to 𝑣, there is 𝑥 ∈ 𝑉(𝐾𝑚) so that 𝑑(𝑢,𝑥) = 1 

and 𝑑(𝑥,𝑣) = 1. Therefore 𝑑(𝑢,𝑣) = 2.  Thus 𝑑(𝑢,𝑣) = {
1,
2,
   gcd(𝑢,𝑣) = 1

  gcd(𝑢,𝑣) ≠ 1
. 

(iii) Suppose 𝑢 ∈ 𝑉(𝐾𝑚) ,𝑣 ∈ 𝑉(𝐻), then 𝑑(𝑢,𝑣) = 1 because every vertex in 𝐾𝑚 is adjacent 
to all vertices in 𝐻. 

From all possibilities (i), (ii), and (iii) it is proven that 𝑑(𝑢,𝑣) ≤ 2.         
 

Corollary 7.  Let 𝑢,𝑣 ∈ 𝑉(𝐺ℤ𝑛), 𝑑(𝑢,𝑣) = 2 if and only if 𝑢 is not relatively prime to 𝑣. 

Proof. It is clear, is a direct result of Theorem 6. 
  

The vertices in the group 𝑝0 apart from forming a complete subgraph of 𝐺ℤ𝑛 are also 

adjacent to all vertices in 𝐺ℤ𝑛. Due to this specific property, in determining the elements of 

the resolving set, only one vertex is allowed. On the other hand, the vertices in the group of 
multiples 𝑝𝑖 also have a specific property. Two groupings of vertices in 𝐺ℤ𝑛, each group have 

specific properties, so it is impossible for the metric bases of 𝐺ℤ𝑛 consist of vertices in the 

group 𝑝0 or in the group of multiples 𝑝𝑖 only. This condition is illustrated in Theorem 8 below 
by observing the vertices in the group 𝑝0. 
 
Theorem 8. Every subset of 𝐾𝑚 is not a resolving set. 
Proof. Referring to Theorem 4, the vertices in group 𝑝0 form a complete subgraph with 𝑚 
vertices and the metric dimension is 𝑚 − 1. That is, the representation of other vertices in 
the group 𝑝0 against the 𝑚 − 1 vertices is the same as the vertex representation outside the 
group 𝑝0 for the 𝑚 − 1 verices. As a result, the set consisting of 𝑚 − 1 vertices is not a 
resolving set. The same condition also applies to sets whose element are less than 𝑚 − 1 
vertices. Based on Theorem 5 which states 𝐺ℤ𝑛 ≅ 𝐾𝑚 +𝐻, it is obtained that each vertex in 

𝐾𝑚 is adjacent to every vertex in 𝐻, it means that the distance is 1. For the same reason, any 
vertex taken from 𝐾𝑚 is not a resolving set. Evidently, every subset of 𝐾𝑚 is not a resolving 
set.        
 

Based on the proof of Theorem 8, the resolving set can not contain only vertices in 𝐾𝑚.  
On the other hand, the vertices in groups of multiples 𝑝1,𝑝2, ..., 𝑝𝑘 has a similar property that 
are not adjacent to each other. Representation of two different vertices of a certain group of 
multiple to another vertices in the same group of multiple and to different groups of multiple 
are presented in the following Lemma 9 and Lemma 10. 
 
Lemma 9.  If 𝑢,𝑣 ∈ 𝑃𝑖, where 𝑢 ≠ 𝑣, then 𝑟(𝑢|𝑃𝑖 ∖ {𝑢,𝑣}) = 𝑟(𝑣|𝑃𝑖 ∖{𝑢,𝑣}).  
Proof. The vertices in the group of multiples 𝑝𝑖 have a similar characteristic, namely they are 
not adjacent. Based on the proof of Theorem 6 (ii) a, the distance between different vertices 
is 2.  Thus, 𝑟(𝑢|𝑃𝑖 ∖{𝑢,𝑣}) = (2,2,…,2) and 𝑟(𝑣|𝑃𝑖 ∖{𝑢,𝑣}) = (2,2,…,2).  
Therefore, 𝑟(𝑢|𝑃𝑖 ∖ {𝑢,𝑣}) = 𝑟(𝑣|𝑃𝑖 ∖{𝑢,𝑣}).        
 
Lemma 10.  If 𝑢,𝑣 ∈ 𝑃𝑗1, then 𝑟(𝑢|𝑃𝑗2) = 𝑟(𝑣|𝑃𝑗2), where 1 ≤ 𝑗1, 𝑗2 ≤ 𝑘 and 𝑢,𝑣 ∉ 𝑃𝑗1 ∩𝑃𝑗2. 



The Metric Dimension and Local Metric Dimension of Relative Prime Graph  
 

Fatmawati  157 

Proof. Based on the proof of Theorem 6 (ii) b, the distance between two vertices on different 
partitions is 1 or 2. Furthermore, 𝑟(𝑢|𝑃𝑗2) = (𝑑(𝑢,𝑝𝑗2),𝑑(𝑢,2𝑝𝑗2),𝑑(𝑢,3𝑝𝑗2),…,𝑑(𝑢,𝑡𝑝𝑗2)) 

and 𝑟(𝑣|𝑃𝑗2) = (𝑑(𝑣,𝑝𝑗2),𝑑(𝑣,2𝑝𝑗2),𝑑(𝑣,3𝑝𝑗2),…,𝑑(𝑣,𝑡𝑝𝑗2)), where 𝑡𝑝𝑗2 ≤ 𝑛 − 1. The 

distance between two vertices in different groups of multiples is 1 if the two vertices are 
relatively prime and the distance is 2 if they are not relatively prime. Since the properties of 
the group of multiples 𝑝𝑗1 and multiples 𝑝𝑗2 are similar, namely that the vertices are not 

adjacent in each group, while 𝑢 and 𝑣 are vertices in the same multiple group, then 
𝑟(𝑢|𝑃𝑗2) = 𝑟(𝑣|𝑃𝑗2).       
 

Based on the results of Lemma 9 and Lemma 10, the vertices in the group of multiple 
𝑝𝑖 become element of the resolving set leaving only one vertex in each group. This also 
applies to the vertices in the group 𝑝0, which leaves only one vertex. Suppose that the vertex 
that must be left in the group of multiples 𝑝𝑖 are 𝑎𝑖 where 1 ≤ 𝑖 ≤ 𝑘 and the vertex that must 
be left in the group 𝑝0 are 𝑎0, the following is given the metric dimension of 𝐺ℤ𝑛. 

 
Theorem 11. 𝐷𝑖𝑚(𝐺ℤ𝑛) = 𝑛 − 𝑘 −2,  where 𝑘 represents number of groups of multiples 

𝑝𝑖, 𝑖 = 1,2,…,𝑘. 
Proof. Suppose 𝑊 = 𝑄0 ∪ 𝑄1 ∪ 𝑄2 ∪…∪𝑄𝑘, where 

𝑄0 = 𝑃0 ∖ {𝑎0},  𝑎0  is an arbitrary vertex left from the group 𝑝0, 
𝑄1 = 𝑃1 ∖ {𝑎1},  𝑎1  is an arbitrary vertex left from the group of multiple 𝑝1, 
𝑄2 = 𝑃2 ∖ {𝑎2},  𝑎2  is an arbitrary vertex left from the group of multiple 𝑝2, 

⋮ 

𝑄𝑘 = 𝑃𝑘 ∖ {𝑎𝑘},  𝑎𝑘  is an arbitrary vertex left from the group of multiple 𝑝𝑘. 
The representation of every vertex in  𝑉(𝐺ℤ𝑛 ∖𝑊) with respect to 𝑊 is: 

𝑟(𝑎0|𝑊) = ( 1,1,1,…,1⏟      
as many as |𝑃0|−1 

, 1,1,1,…,1⏟      
as many as |𝑃1|−1 

, 1,1,1,…,1⏟      
as many as |𝑃2|−1 

,…, 1,1,1,…,1⏟      
as many as |𝑃𝑘|−1 

)  

𝑟(𝑎1|𝑊) = ( 1,1,1,…,1⏟      
as many as |𝑃0|−1 

, 2,2,2,…,2⏟      
as many as |𝑃1|−1 

,𝑑(𝑎1,𝑄2),…,𝑑(𝑎1,𝑄𝑘)) 

𝑟(𝑎2|𝑊) = ( 1,1,1,…,1⏟      
as many as |𝑃0|−1 

,𝑑(𝑎2,𝑄1), 2,2,2,…,2⏟      
as many as |𝑃2|−1 

,…,𝑑(𝑎2,𝑄𝑘)) 

⋮ 

𝑟(𝑎𝑘|𝑊) = ( 1,1,1,…,1⏟      
as many as |𝑃0|−1 

, 𝑑(𝑎𝑘,𝑄1), 𝑑(𝑎𝑘,𝑄2),…, 2,2,2,…,2⏟      
as many as |𝑃𝑘|−1 

)  

where  𝑑(𝑎𝑖,𝑄𝑗) = {

1,if 𝑎𝑖 ∉ 𝑃𝑗

2, if 𝑎𝑖 ∈ 𝑃𝑗

  ,   1 ≤ 𝑖,𝑗 ≤ 𝑘. 

It appears that the representation of every vertex with respect to 𝑊 is different, so that 𝑊 is 
a resolving set. Next, it will be shown that the cardinality of 𝑊 is minimal. Suppose that any 
set 𝑋 is taken whose cardinality is one less than 𝑊, that is, |𝑋| = |𝑊|− 1. There are three 
possibilities for elements of set 𝑋, namely (i) all vertices in group 𝑝0 are element of 𝑋; (ii) all 
vertices in the group of multiples 𝑝𝑖 are element of 𝑋; and (iii) all vertices of the group of 
multiple 𝑝𝑗 (certain 𝑗), 1 ≤ 𝑗 ≤ 𝑘 being element of 𝑋. 

(i) If all vertices in the group 𝑝0 are element of 𝑋, then 𝑘 + 1 of the vertices in 𝐺ℤ𝑛 must be 

left in the group of multiples  𝑝𝑖 with the number of groups being 𝑘. 
a. Suppose that as many as 𝑘 − 1 groups leave each one vertex, then there are two 

vertices that must be left by the group of multiple 𝑝𝑗 (certain 𝑗), 1 ≤ 𝑗 ≤ 𝑘. Due to 



The Metric Dimension and Local Metric Dimension of Relative Prime Graph  
 

Fatmawati  158 

the similar properties of vertices in the group of multiple 𝑝𝑗, the representation of 

the two vertices with respect to 𝑋 will be the same. Thus 𝑋 is not being a resolving 
set. 

b. Suppose that all vertices in the 𝑘 − 1  group are element of 𝑋, then there is one 
particular group, name the group of multiple 𝑝𝑗 (certain 𝑗), 1 ≤ 𝑗 ≤ 𝑘 leaving 𝑘 + 1 

vertex. For the same reason as (i)a, these 𝑘 − 1  vertices will have the same 
representation of 𝑋 because the vertices in the group of multiples 𝑝𝑗 are non-

mutually adjacent. So 𝑋 is not a resolving set. 
(ii) If all the vertices in the group of multiples 𝑝𝑖 are element of 𝑋, then |𝑋| = |𝑊| − 1+

𝑘 = (𝑛 − 2 − 𝑘) − 1+ 𝑘 = 𝑛 − 3 ≥ 𝑛 − 2− 𝑘 for 𝑘 ≥ 1. The equity hold only to 𝑘 = 1. 
So, for 𝑘 ≥ 2 then |𝑋| > |𝑊|. This contradicts the cardinality of the set 𝑋. 

(iii) If all vertices in a group of multiples 𝑝𝑖, namely 𝑝𝑗 dengan 1 ≤ 𝑗 ≤ 𝑘 as element of 𝑋, 

then from the vertices in 𝐺ℤ𝑛 must be left 𝑘 + 1 vertices in 𝑘 − 1 group of multiples 𝑝𝑖 

(other than 𝑝𝑗) and in the group 𝑝0. 

a. Suppose that all vertices in the group 𝑝0 are element of 𝑋, then from 𝑘 − 1 group of  
multiples 𝑝𝑖 must be left 𝑘 vertices. This is similar to case (i). 

b. Suppose all vertices in the group of multiples 𝑝𝑖 (other than 𝑝𝑗) are element of 𝑋, it 

means that all vertices in the group of multiples 𝑝𝑖 are element of 𝑋. This is similar 
to the case (ii). 

From all of the above possibilities it can be concluded that 𝑋 is not a resolving set. If all 
vertices in one group are selected as element of set 𝑋, then 𝑋 is not a resolving set. Likewise, 
if there is a group 𝑝0 or a group of multiples 𝑝𝑖 that leaves more than one vertex, it will result 
that 𝑋 not being a resolving set. Since |𝑋| = |𝑊| − 1 and 𝑊 are resolving set, it means that 
𝑊 is the resolving set with minimal cardinality or the metric bases of 𝐺ℤ𝑛. Since each group 

leaves one vertex and the number of groups are 𝑘 +1, the metric dimension of 𝐺ℤ𝑛 is 

(𝑛 − 1) − (𝑘 + 1) = 𝑛 − 𝑘 − 2. It is proven that 𝑑𝑖𝑚(𝐺ℤ𝑛) = 𝑛 −𝑘 − 2.       

 
Based on Theorem 11, the metric bases of 𝐺ℤ𝑛 consists of a combination of vertices in 

the group 𝑝0 and the group of multiples 𝑝𝑖 with the conditions each leaving only one vertex. 
The final part of this research is to determine the value of the local metric dimension of 𝐺ℤ𝑛 

by first determining the local resolving set. In this case the vertex representation may be the 
same as long as the vertices are not adjacent. 

 
Theorem 12. 𝐷𝑖𝑚𝑙(𝐺ℤ𝑛) = |𝑃0| + 𝑘 − 1, where 𝑘 representing number of groups of multiples 

𝑝𝑖, 𝑖 = 1,2,…,𝑘  and |𝑃0|  is the cardinality of set 𝑃0. 
Proof. Based on the property of each group of multiples 𝑝𝑖, 𝑖 = 1,2,…,𝑘, which the vertices 
are not mutually adjacent, the property of the group 𝑝0 that all elements are adjacent to 
every vertex, and according to the definition of the local metric dimension, then we choose 
the set  𝑊𝑙 = {1,𝑝01,…,𝑝𝑜(𝑚−2),𝑝11,𝑝21,…,𝑝𝑘1},  where 

1,𝑝01,…,𝑝𝑜(𝑚−2) are 𝑚 − 1 vertices in the group 𝑝0, 

𝑝11 is one vertex in the group of multiples 𝑝1, 
𝑝21 is one vertex in the group of multiples 𝑝2, 
𝑝𝑘1 is one vertex in the group of multiples 𝑝𝑘.  

The representation of every vertex in 𝐺ℤ𝑛 with respect to 𝑊𝑙 is: 

𝑟(1|𝑊𝑙) = (0,1,…,1,1,1,…,1);   𝑟(𝑝01|𝑊𝑙) = (1,0,…,1,1,1,…,1);  

𝑟(𝑝𝑜(𝑚−2)|𝑊𝑙) = (1,1,…,0,1,1,…,1);   𝑟(𝑝11|𝑊𝑙) = (1,1,…,1,0,1,…,1); 

𝑟(𝑝21|𝑊𝑙) = (1,1,…,1,1,0,…,1);   𝑟(𝑝𝑘1|𝑊𝑙) = (1,1,…,1,1,1,…,0); 



The Metric Dimension and Local Metric Dimension of Relative Prime Graph  
 

Fatmawati  159 

𝑟(𝑝02|𝑊𝑙) = (1,1,…,1,1,1,…,1);   𝑟(𝑝03|𝑊𝑙) = (1,1,…,1,1,1,…,1); 
𝑟(𝑝12|𝑊𝑙) = (1,1,…,1,2,2,…,1);   𝑟(𝑝13|𝑊𝑙) = (1,1,…,1,2,2,…,1); 
𝑟(𝑝14|𝑊𝑙) = (1,1,…,1,2,2,…,1);   𝑟(𝑝1𝑠|𝑊𝑙) = (1,1,…,1,2,2,…,1). 

It appears that 𝑟(𝑝13|𝑊𝑙) = 𝑟(𝑝13|𝑊𝑙) = 𝑟(𝑝14|𝑊𝑙) = 𝑟(𝑝1𝑠|𝑊𝑙), but 𝑝12,𝑝13,𝑝14,𝑝1𝑠 
are vertices in the group of multiples 𝑝1 which is not mutually adjacent. In the concept of 
local metric dimensions, the above still meets the criteria, meaning that 𝑊𝑙 is a local 
resolving set. Next, it will be shown that the cardinality of 𝑊𝑙 is minimal. Suppose any set 𝑋𝑙 
whose cardinality is reduced to one from the set 𝑊𝑙, i.e. |𝑋𝑙| = |𝑊𝑙| − 1. There are three 
possibilities for element of 𝑋𝑙, namely (i) all vertices in group 𝑝0 become element of 𝑋𝑙; (ii) 
at least one vertex from each group of multiples 𝑝𝑖 become element of 𝑋𝑙; and (iii) the group 
𝑝0 leaves more than one vertex. 

(i) Suppose that all vertices in the group 𝑝0 are members of 𝑋𝑙, then there are 𝑘 − 2  
vertices from the group of multiple 𝑝𝑖 as many as 𝑘 that can be element of 𝑋𝑙. Assuming 
at least one vertex in each group of multiple 𝑝𝑖 becomes a element of 𝑋𝑙, it means that 
there are at least two groups whose vertices are not represented as element of 𝑋𝑙. It is 
sufficient to show that there are two vertices from two different groups, these two 
vertices are adjacent and have the same representation respect to 𝑋𝑙. Suppose that the 
two groups not represented in the element of the set 𝑋𝑙 are the group of multiples 𝑝𝑗1 

and 𝑝𝑗2 where 1 ≤ 𝑗1, 𝑗2 ≤ 𝑘.  Vertex 𝑝𝑗1 is adjacent to 𝑝𝑗2 because both are prime 

numbers and are the first element in their respective group of multiples. In addition, 
vertices 𝑝𝑗1 and 𝑝𝑗2 are adjacent to all vertices in the group 𝑝0, so that 𝑟(𝑝𝑗1|𝑋𝑙) =

𝑟(𝑝𝑗2|𝑋𝑙). Consequently, 𝑋𝑙 is not a resolving set. 

(ii) Suppose that at least one vertex from each group of multiples 𝑝𝑖 is a element of 𝑋𝑙, then 
there are at least two vertices in the group 𝑝0 that are not element of 𝑋𝑙. The two 
vertices in the group 𝑝0 will have the same representation respect to 𝑋𝑙, because the 
two vertices in the group 𝑝0 are adjacent to every vertex in 𝐺ℤ𝑛. So 𝑋𝑙 is not a resolving 

set. 
(iii) Suppose that the group 𝑝0 leaves more than one vertex, then 

a. If the group 𝑝0 leaves two vertices, then whatever the condition for selecting 
vertices in the group of multiples 𝑝𝑖, the remaining two vertices in the group 𝑝0 will 
have the same representation respect to 𝑋𝑙. Consequently,  𝑋𝑙 is not a resolving set. 

b. If the group 𝑝0 leaves more than two vertices, then there is a group of multiples 𝑝𝑖 
where all the vertices are not 𝑋𝑙 element. In this case, the remaining vertices in the 
group 𝑝0 will have the same representation of 𝑋𝑙 regardless of the vertex conditions 
in the group of multiples 𝑝𝑖. As a result, 𝑋𝑙 is not a resolving set. 

From all of the above possibilities, it can be concluded that 𝑋𝑙 is not a local resolving set. If 
there are more than one vertex left in group 𝑝0, then the representation of the remaining 
vertices respect to 𝑋𝑙 will be the same. Likewise, if there is one or more groups of multiples 
𝑝𝑖 that are not represented in the element of the set 𝑋𝑙, it can always be found the vertices of 
the group of multiples 𝑝𝑖 which have the same representation respect to set 𝑋𝑙 eventhough 
they are adjacent. Since |𝑋𝑙| = |𝑊𝑙| − 1 and 𝑊𝑙 are local resolving set, it can be concluded 
that 𝑊𝑙 is a local resolving set with minimal cardinality or local metric bases of 𝐺ℤ𝑛. The 

cardinality of the set 𝑊𝑙 is the local metric dimension of 𝐺ℤ𝑛.  

It is proven  that  𝑑𝑖𝑚𝑙(𝐺𝑍𝑛) = |𝑃0|− 1 + 𝑘.        

Based on Theorem 12, the local metric bases consists of vertices in the group 𝑝0 and the 
group of multiples 𝑝𝑖, provided that the group 𝑝0 leaves only one vertex while in each group 
of multiples 𝑝𝑖 are represented by only one vertex. 



The Metric Dimension and Local Metric Dimension of Relative Prime Graph  
 

Fatmawati  160 

Example: Suppose given 𝐺ℤ17, where 𝑉(𝐺ℤ17) = {1,2,3,…, 16}. It will determine the metric 

dimension and the local metric dimension of 𝐺ℤ17 and some metric bases and local metric 

bases. Firstly, the vertices of  𝐺ℤ17 were grouped as follows: 

Group 𝑝0:1,11,13  then |𝑃0| = 3. 
Group of multiple 2 are 2,4,6,8,10,12,14,16. 
Group of multiple 3 are 3,6,9,12,15. 
Group of multiple 5 are 5,10,15. 
Group of multiple 7 are 7,14. 

There are four groups of multiples, namely multiples of 2, multiples of 4, multiples of 5, and 
multiples of 7, so 𝑘 = 4.  
(1) 𝑑𝑖𝑚(𝐺ℤ17) = 17 − 4 − 2 = 11. Some of the metric bases of 𝐺ℤ17 are: 

- 𝑊1 = {1,11,2,3,4,6,8,10,12,14,15}, then 
𝑟(5|𝑊1) = (1,1,1,1,1,1,1,2,1,1,2);  𝑟(7|𝑊1) = (1,1,1,1,1,1,1,1,1,2,1); 
𝑟(9|𝑊1) = (1,1,1,2,1,2,1,1,2,1,2);  𝑟(13|𝑊1) = (1,1,1,1,1,1,1,1,1,1,1); 
𝑟(16|𝑊1) = (1,1,2,1,2,2,2,2,2,2,1). 

- 𝑊2 = {1,13,2,3,4,6,10,12,14,15,16}, then 
𝑟(5|𝑊2) = (1,1,1,1,1,1,2,1,2,2,1);  𝑟(7|𝑊2) = (1,1,1,1,1,1,1,1,2,1,1); 
𝑟(8|𝑊2) = (1,1,2,1,2,2,2,2,2,1,2);  𝑟(9|𝑊2) = (1,1,1,2,1,2,1,2,1,2,1);  
𝑟(11|𝑊2) = (1,1,1,1,1,1,1,1,1,1,1). 

- 𝑊3 = {11,13,2,4,6,9,10,12,14,15,16}, then 
𝑟(1|𝑊3) = (1,1,1,1,1,1,1,1,1,1,1);  𝑟(3|𝑊3) = (1,1,1,1,1,2,2,1,2,2,1); 
𝑟(5|𝑊3) = (1,1,1,1,1,1,2,1,1,2,1);  𝑟(7|𝑊3) = (1,1,1,1,1,1,1,1,2,1,1);  
𝑟(8|𝑊3) = (1,1,2,1,2,1,2,2,2,1,2). 

(2) 𝑑𝑖𝑚𝑙(𝐺ℤ17) = 3 − 1+ 4 = 6. Some of the local metric bases of 𝐺ℤ17 are: 

- 𝑊𝑙1 = {1,11,2,3,5,7}, then 

𝑟(4|𝑊𝑙1) = (1,1,2,1,1,1);  𝑟(6|𝑊𝑙1) = (1,1,2,2,1,1);  𝑟(8|𝑊𝑙1) = (1,1,2,1,1,1); 

𝑟(9|𝑊𝑙1) = (1,1,1,2,1,1);  𝑟(10|𝑊𝑙1) = (1,1,2,1,2,1);  𝑟(12|𝑊𝑙1) = (1,1,2,2,1,1); 

𝑟(13|𝑊𝑙1) = (1,1,1,1,1,1);  𝑟(14|𝑊𝑙1) = (1,1,2,1,1,2); 

𝑟(15|𝑊𝑙1) = (1,1,1,2,2,1);  𝑟(16|𝑊𝑙1) = (1,1,2,1,1,1). 

  It appears that 𝑟(4|𝑊𝑙1) =  𝑟(8|𝑊𝑙1) and 𝑟(6|𝑊𝑙1) =  𝑟(12|𝑊𝑙1), but vertex 4 is not 

adjacent to 8 and vertex 6 is not adjacent to 12. 
- 𝑊𝑙2 = {1,13,4,9,5,7}, then 

𝑟(2|𝑊𝑙2) = (1,1,2,1,1,1);  𝑟(3|𝑊𝑙2) = (1,1,1,1,1,1);  𝑟(6|𝑊𝑙2) = (1,1,2,2,1,1);  

𝑟(8|𝑊𝑙2) = (1,1,2,1,1,1);  𝑟(10|𝑊𝑙2) = (1,1,2,1,2,1);  𝑟(11|𝑊𝑙2) = (1,1,1,1,1,1);  

𝑟(12|𝑊𝑙2) = (1,1,2,2,1,1);  𝑟(14|𝑊𝑙2) = (1,1,2,1,1,2);  

𝑟(15|𝑊𝑙2) = (1,1,1,2,2,1);  𝑟(16|𝑊𝑙2) = (1,1,2,1,1,1). 

It appears that 𝑟(2|𝑊𝑙1) =  𝑟(8|𝑊𝑙1) and 𝑟(6|𝑊𝑙1) =  𝑟(12|𝑊𝑙1), but vertex 2 is not 

adjacent to 8 and vertex 6 is not adjacent to 12. 
- 𝑊𝑙3 = {1,11,8,12,5,14},  then  

𝑟(2|𝑊𝑙3) = (1,1,2,2,1,2);  𝑟(3|𝑊𝑙3) = (1,1,1,2,2,1);  𝑟(4|𝑊𝑙3) = (1,1,2,2,1,2);  

𝑟(6|𝑊𝑙3) = (1,1,2,2,1,2);  𝑟(7|𝑊𝑙3) = (1,1,1,1,1,1);  𝑟(9|𝑊𝑙3) = (1,1,1,2,1,1);  

𝑟(10|𝑊𝑙3) = (1,1,2,2,2,2);  𝑟(13|𝑊𝑙3) = (1,1,1,1,1,1);  

𝑟(15|𝑊𝑙3) = (1,1,1,2,2,1);  𝑟(16|𝑊𝑙3) = (1,1,2,2,1,2). 

It appears that 𝑟(2|𝑊𝑙3) = 𝑟(4|𝑊𝑙3) = 𝑟(6|𝑊𝑙3) = 𝑟(16|𝑊𝑙3), but the vertices 2,4,6,16 

are not adjacent to each other. 



The Metric Dimension and Local Metric Dimension of Relative Prime Graph  
 

Fatmawati  161 

CONCLUSIONS 

This research focuses on determining the metric dimension and local metric dimension 
of relative prime graphs 𝐺𝑍𝑛. Based on the previous discussion, it can be concluded that: 

(1)  𝑑𝑖𝑚(𝐺𝑍𝑛) = 𝑛 −𝑘 − 2;   

(2) 𝑑𝑖𝑚𝑙(𝐺𝑍𝑛) = |𝑃0| − 1 + 𝑘, 

where 𝑘 is the number of group multiples 𝑝1,𝑝2,…,𝑝𝑘, and |𝑃0| is the cardinality of set 𝑃0. 

In the future, the research can be extended to other topics such as fractional metric 
dimensions, local fractional metric dimensions, domination numbers/set, graph coloring, 
and graph labeling as well as expansion of research objects in special rings. 

 
 

REFERENCES 

 

[1]  G. Chartrand and L. Lesniak, Graphs and Digraphs, Third Edition, Chapman & Hall/CRC, 
Florida, 2000. 

[2]  P. J. Slater, "Leaves and trees", Congr. Numer., 14, pp. 549-559, 1975. 

[3]  F. Harary and R. A. Melter, "On the Metric Dimension of a Graph", Ars Combinatoria, 
Vol. 2,  pp. 191-195, 1976. 

[4]  J. A. Rodriquez-Velazquez, I. G. Yero, D. Kuziak and O. R. Oellermann,  "On the strong 
metric dimension of cartesian and direct product of graphs", Discrete Mathematics 
335, pp. 8-19, 2014. 

[5]  F. Okamoto, B. Phinezy and P. Zhang, "The Local Metric Dimension of a graph", Math. 
Bohem., Vol. 135, pp. 239-255, 2010. 

[6]  I. Beck, "Coloring of Commutative Rings", Journal of Algebra, Vol. 116, No.1, pp. 208-
226, 1988. 

[7] D. F. Anderson and P. S. Livingston, "The Zero-Divisor Graph of a Commutative Ring", 
Journal of Algebra 217, pp. 434-447 1999. 

[8] S. P. Redmond, "The zero-divisor graph of a non-commutative ring", International J. 
Commutative Rings 1(4), pp. 203-211, 2002. 

[9] S. P. Redmond, "Central Sets and Radii of the Zero-Divisor Graphs of Commutative 
Rings", Communications in Algebra 34, pp. 2389–2401, 2006. 

[10] A. Azimi, A. Erfanian and D. G. Farrokhi,  "The Jacobson Graph of Commutative Rings", 
Jounal of Algebra and its Application, DOI: 10.1142/S0219498812501794, 2012. 

[11] A. Novictor, L. Susilowati and Fatmawati, "Jacobson graph construction of ring Z3n, for 
n > 1", Journal of Physics: Conference Series 1494 (2020) 012016, doi:10.1088/1742-
6596/1494/1/012016, 2020. 

[12] J. B. Fraleigh, A First Course in Abstract Algebra, Addison-Wesley Publishing Company,  
Massachusetts, 2003. 

[13] G. Chartrand, L. Eroh, M. A. Johnson and O. R. Oellermann, "Resolvability in graphs and 
the metric dimension of a graph", Discrete Applied Mathematics 105, pp. 99-113, 2000.