On The Local Metric Dimension of Line Graph of Special Graph


CAUCHY – JURNAL MATEMATIKA MURNI DAN APLIKASI 
Volume 4(3) (2016), Pages 125-130 
 

Submitted: October, 04 2016 Reviewed: October, 21 2016 Accepted: November, 29 2016 

DOI: http://dx.doi.org/10.18860/ca.v4i3.3694 

 

On The Local Metric Dimension of Line Graph of Special Graph 

Marsidi1, Dafik2 ,Ika Hesti Agustin3, Ridho Alfarisi4 

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

3Mathematics Depart. University of Jember Indonesia 
4Mathematics Depart. ITS Surabaya Indonesia 

Email: marsidiarin@gmail.com, d.dafik@gmail.com, ikahestiagustin@gmail.com, alfarisi38@gmail.com. 

ABSTRACT 

Let G be a simple, nontrivial, and connected graph. 𝑊 = {𝑤1,𝑤2,𝑤3 ,… ,𝑤𝑘} is a representation of an ordered 
set of k distinct vertices in a nontrivial connected graph G. The metric code of a vertex v, where 𝑣 ∈ G, the 

ordered 𝑟(𝑣|𝑊) = (𝑑(𝑣,𝑤1),𝑑(𝑣,𝑤2), . . . ,𝑑(𝑣,𝑤𝑘)) of k-vector is representations of v with respect to W, 

where 𝑑(𝑣,𝑤𝑖) is the distance between the vertices v and wi for 1≤ i ≤k.  Furthermore, the set W is called a 
local resolving set of G if  𝑟(𝑢|𝑊) ≠  𝑟(𝑣|𝑊) for every pair u,v of adjacent vertices of G. The local metric 
dimension ldim(G) is minimum cardinality of W. The local metric dimension exists for every nontrivial 
connected graph G. In this paper, we study the local metric dimension of line graph of special graphs , namely 

path, cycle, generalized star, and wheel. The line graph L(G) of a graph G has a vertex for each edge of G, 
and two vertices in L(G) are adjacent if and only if the corresponding edges in G have a vertex in common.  

 
Keywords: metric dimension, local metric dimension number, line graph, resolving set. 

INTRODUCTION 

All graph in this paper are simple, nontrivial, and undirected, for more detail basic 
definition of graph, see [1]. In [2] define the distance 𝑑(𝑢,𝑣) between two vertices u and v in a 
connected graph G is the length of a shortest path between these two vertices. Suppose that 𝑊 =
{𝑤1,𝑤2,𝑤3 ,… ,𝑤𝑘}  is an ordered set of vertices of a nontrivial connected graph G. The metric 

representation of v with respect to W is the k-vector 𝑟(𝑣|𝑊) = (𝑑(𝑣,𝑤1),𝑑(𝑣,𝑤2), . . . ,𝑑(𝑣,𝑤𝑘)). 

Distance in graphs has also been used to distinguish all of the vertices of a graph. The set W is 
called a resolving set for G if distinct vertices of G have distinct representations with respect to W.  
The metric dimension dim(G) of G is the minimum cardinality of resolving set for G [3]. 
Furthermore, we consider those ordered sets W of vertices of G for which any two vertices of G 
having the same code with respect to W are not adjacent in G. If 𝑟(𝑢|𝑊) ≠  𝑟(𝑣|𝑊)  for every pair 
u, v of adjacent vertices of G, then W is called a local metric set of G. The minimum k for which G 
has a local metric k-set is the local metric dimension of G, which is denoted by ldim(G) [4]. 

In this paper, we study the local metric dimension number of line graph of special graphs, 
namely path, cycle, generalized star, and wheel graph. Line graphs are a special case of 
intersection graphs. The line graph L(G) of a graph G has a vertex for each edge of G, and two 
vertices in L(G) are adjacent if and only if the corresponding edges in G have a vertex in common. 
Thus, the line graph L(G) is the intersection graph corresponding to the endpoint sets of the edges 

http://dx.doi.org/10.18860/ca.v4i3.3694
mailto:marsidiarin@gmail.com
mailto:d.dafik@gmail.com
mailto:ikahestiagustin@gmail.com
mailto:alfarisi38@gmail.com


On The Local Metric Dimension of Line Graph of Special Graph 

Marsidi 126 

of G. As for an example, Figure 1 shows a graph G and its line graph L(G) [5]. The results show that 
distinct vertices of each L(G), with G is a special graph, namely path, cycle, generalized star, and 
wheel graph have distinct representations with respect to W, and their local metric dimension 
attain a minimum number. Furthermore, [6] showed that on the metric dimension, the upper 

dimension and the resolving number of graphs, [7] showed the metric dimension of 
amalgamation of cycles,  [8] studied the constant metric dimension of regular graphs, [2] obtained 
resolvability in graphs and the metric dimension of a graph. The last, [9] showed the Fault-tolerant 
metric and partition dimension of graph.  

 
                                         Figure 1. A graph and its line graph 

 
 

RESULTS AND DISCUSSIONS 

We have some observation to show the result of line graph of path, cycle, generalized star, 
and wheel graph. Thus, we have four main theorem about local metric dimension to discuss as 
follows. 

 
Observation 1. The order and the size of 𝐿(𝑃𝑛) are |𝑉(𝐿(𝑃𝑛))| = 𝑛−1 and |𝐸(𝐿(𝑃𝑛))| = 𝑛−2, 

respectively. 
Proof. Line graph of Path 𝐿(𝑃𝑛) is connected, simple, and undirected graph with vertex set 
𝑉(𝐿(𝑃𝑛)) = {𝑣𝑖;1 ≤ 𝑖 ≤ 𝑛−1} and edge set 𝐸(𝐿(𝑃𝑛)) = {𝑣𝑖𝑣𝑖+1;1 ≤ 𝑖 ≤ 𝑛−2}. Thus, 

|𝑉(𝐿(𝑃𝑛))| = 𝑛−1 and |𝐸(𝐿(𝑃𝑛))| = 𝑛−2. See Figure 2 (a) and 2 (b) for illustration.                    ∎ 
 

Theorem 1. For 𝑛 ≥ 2, the local metric dimension of line graph of path is 𝑙𝑑𝑖𝑚(𝐿(𝑃𝑛)) = 1. 

Proof. By observation 1, line graph of path 𝐿(𝑃𝑛) is isomorphic to 𝑃𝑛−1. Thus, the vertex set and 
the edge set of 𝐿(𝑃𝑛) are 𝑉(𝐿(𝑃𝑛)) = {𝑣𝑖;1 ≤ 𝑖 ≤ 𝑛−1} and 𝐸(𝐿(𝑃𝑛)) = {𝑣𝑖𝑣𝑖+1;1 ≤ 𝑗 ≤ 𝑛−2}, 

respectively. The number of vertices |𝑉(𝐿(𝑃𝑛))| = 𝑛−1 and the size |𝐸(𝐿(𝑃𝑛))| = 𝑛−2.  By 

Theorem 3, 𝑙𝑑𝑖𝑚(𝑃𝑛) = 1, thus 𝑙𝑑𝑖𝑚(𝐿(𝑃𝑛)) = 1. It concludes the proof. See Figure 2 (c) for 

illustration .                                                                                                                             ∎ 
  

 
Figure 2. (a) 𝑃8  , (b) 𝐿{𝑃8},  (c) Construction of local resolving set 𝑊 = {𝑣1} 

 
Observation 2. The order and the size of 𝐿(𝐶𝑛) are |𝑉(𝐿(𝐶𝑛)) | = 𝑛 and |𝐸(𝐿(𝑃𝑛))| = 𝑛, 

respectively. 



On The Local Metric Dimension of Line Graph of Special Graph 

Marsidi 127 

Proof. Line graph of cycle 𝐿(𝐶𝑛) is connected, simple, and undirected graph with vertex set 
𝑉(𝐿(𝐶𝑛)) = {𝑣𝑖;1 ≤ 𝑖 ≤ 𝑛} and edge set 𝐸(𝐿(𝐶𝑛)) = {𝑣𝑖𝑣𝑖+1;1 ≤ 𝑗 ≤ 𝑛−1}∪{𝑣𝑛𝑣1;}. Thus, 

|𝑉(𝐿(𝐶𝑛))| = 𝑛 and |𝐸(𝐿(𝐶𝑛))| = 𝑛. See Figure 3 (a) and 3 (b) for illustration.                                 ∎ 
 

Theorem 2. For 𝑛 ≥ 3, the local metric dimension of line graph of cycle is 

𝑙𝑑𝑖𝑚(𝐿(𝐶𝑛)) = {
 1, 𝑓𝑜𝑟  𝑛 𝑒𝑣𝑒𝑛
2,        𝑓𝑜𝑟  𝑛 𝑜𝑑𝑑

 

Proof. By observation 2, line graph of cycle 𝐿(𝐶𝑛) is isomorphic to 𝐶𝑛. Thus, the vertex set and the 

edge set of 𝐿(𝐶𝑛) are 𝑉(𝐿(𝐶𝑛)) = {𝑣𝑖;1 ≤ 𝑖 ≤ 𝑛} and 𝐸(𝐿(𝐶𝑛)) = {𝑒𝑗;1 ≤ 𝑗 ≤ 𝑛}, respectively. 

The order of vertices |𝑉(𝐿(𝐶𝑛))| = 𝑛 and the size |𝐸(𝐿(𝐶𝑛))| = 𝑛.  By Theorem 3,  

𝑙𝑑𝑖𝑚(𝐶𝑛) = {
 1, for 𝑛 even
2,        for 𝑛 odd

 

thus  

𝑙𝑑𝑖𝑚(𝐿(𝐶𝑛)) = {
 1, for 𝑛 even
2,        for 𝑛 odd

 

It concludes the proof. See Figure 3 (c) for illustration.  ∎ 
 

 
Figure 3. (a) 𝐶8  , (b) 𝐿{𝐶8},  (c) Construction of local resolving set 𝑊 = {𝑣1} 

 
Observation 3. The order and the size of 𝐿(𝑆𝑛,𝑚) are |𝑉(𝐿(𝑆𝑛,𝑚))| = 𝑚𝑛 and |𝐸(𝐿(𝑆𝑛,𝑚))| = 𝑚𝑛+
𝑛(𝑛−3)

2
, respectively. 

Proof. Line graph of generalized star 𝐿(𝑆𝑛,𝑚) is connected, simple, and undirected graph with 

vertex set 𝑉(𝐿(𝑆𝑛,𝑚)) = {𝑥𝑖,𝑗;1 ≤ 𝑖 ≤ 𝑛,1 ≤ 𝑗 ≤ 𝑚} and edge set 𝐸(𝐿(𝑆𝑛,𝑚)) = {𝑥𝑖,𝑗𝑥𝑖,𝑗+1;1 ≤ 𝑖 ≤

𝑛,1 ≤ 𝑗 ≤ 𝑚−1}∪{𝑥𝑖,1𝑥𝑡,1; 𝑖 ≠ 𝑡,1 ≤ 𝑖,𝑡 ≤ 𝑛}. Thus, |𝑉(𝐿(𝑆𝑛,𝑚))| = 𝑚𝑛 and |𝐸(𝐿(𝑆𝑛,𝑚))| =

𝑚𝑛+
𝑛(𝑛−3)

2
. See Figure 4 (a) and 4 (b) for illustration.                                                                       ∎ 

 

Theorem 3. For 𝑛 ≥ 3, the local metric dimension of line graph of generalized star is 
𝑑𝑖𝑚(𝐿(𝑆𝑛,𝑚)) = 𝑛−1. 

Proof. By observation 3, the order and the size of 𝐿(𝑆𝑛,𝑚) are |𝑉(𝐿(𝑆𝑛,𝑚))| = 𝑚𝑛 and 

|𝐸(𝐿(𝑆𝑛,𝑚))| = 𝑚𝑛+
𝑛(𝑛−3)

2
, respectively. Suppose the lower bound is 𝑙𝑑𝑖𝑚(𝐿(𝑆𝑛,𝑚)) ≥ 𝑛−2 

with the resolving set 𝑊′ = {𝑥𝑖,1;1 ≤ 𝑖 ≤ 𝑛−2}. Thus two vertices of 𝑉(𝐿(𝑆𝑛,𝑚))−𝑊
′ with 

respect to 𝑊′ are  

𝑟(𝑥𝑛−1,1|𝑊
′) = 𝑟(𝑥𝑛,1|𝑊

′) = ( 1,…,1⏟  
𝑛−2 𝑡𝑖𝑚𝑒𝑠

)  

It is easy to see that the line graph of generalized star has the same vertex representation 
respecting to 𝑊′. Thus, the lower bound is 𝑙𝑑𝑖𝑚(𝐿(𝑆𝑛,𝑚)) ≥ 𝑛−1. Now, we will show that 

𝑙𝑑𝑖𝑚(𝐿(𝑆𝑛,𝑚)) ≤ 𝑛−1 by determining the resolving set 𝑊 = {𝑥𝑖,1;1 ≤ 𝑖 ≤ 𝑛−1} and the vertex 

representation of 𝑉(𝐿(𝑆𝑛,𝑚))−𝑊 respect to 𝑊, as follows 



On The Local Metric Dimension of Line Graph of Special Graph 

Marsidi 128 

𝑟(𝑥𝑛,𝑗|𝑊) = ( 𝑗,…,𝑗⏟  
𝑛−1 𝑡𝑖𝑚𝑒𝑠

);1 ≤ 𝑗 ≤ 𝑚 

𝑟(𝑥𝑖,𝑗|𝑊) = ( 𝑗,…,𝑗⏟  
𝑖−1 𝑡𝑖𝑚𝑒𝑠

, 𝑗−1, 𝑗,…,𝑗⏟  
𝑛−𝑖−1 𝑡𝑖𝑚𝑒𝑠

);1 ≤ 𝑖 ≤ 𝑛−1,2 ≤ 𝑗 ≤ 𝑚 

 

It easy to see that ∀𝑢,𝑣 ∈ 𝑉(𝐿(𝑆𝑛,𝑚))−𝑊 have a different representation respect to W for every 

pair 𝑢,𝑣 of adjacent vertices in 𝐿(𝑆𝑛,𝑚). The cardinality of resolving set 𝐿(𝑆𝑛,𝑚) is 𝑛−1, thus 
𝑙𝑑𝑖𝑚(𝐿(𝑆𝑛)) ≤ 𝑛−1. It concludes the proof. See Figure 4 (c).                                                  ∎ 

 

 
Figure 4. (a) 𝑆6,3,  (b) 𝐿(𝑆6,3), (c) Construction of local resolving set 𝑊 = {𝑥1,1,𝑥2,1,𝑥3,1,𝑥4,1,𝑥5,1} 

 

Observation 4. The order and the size of 𝐿(𝑊𝑛) are |𝑉(𝐿(𝑊𝑛))| = 2𝑛 and |𝐸(𝐿(𝑊𝑛))| =
𝑛(𝑛+5)

2
, 

respectively. 
Proof. Line graph of wheel 𝐿{𝑊𝑛} is connected, simple, and undirected graph with vertex set 

𝑉(𝐿(𝑊𝑛)) = {𝑥𝑖,𝑗;1 ≤ 𝑖 ≤ 𝑛,1 ≤ 𝑗 ≤ 2} and edge set 𝐸(𝐿(𝑆𝑛,𝑚)) = {𝑥𝑖,1𝑥𝑖,2;1 ≤ 𝑖 ≤ 𝑛}∪

{𝑥𝑖,1𝑥𝑡,1; 𝑖 ≠ 𝑡,1 ≤ 𝑖,𝑡 ≤ 𝑛}∪{𝑥𝑖,2𝑥𝑖+1,2;1 ≤ 𝑖 ≤ 𝑛−1}∪{𝑥𝑖,2𝑥𝑖+1,1;1 ≤ 𝑖 ≤ 𝑛−1}∪{𝑥1,2𝑥𝑛,2} 

∪{𝑥1,1𝑥𝑛,2}. Thus, |𝑉(𝐿(𝑊𝑛))| = 2𝑛 and |𝐸(𝐿(𝑊𝑛))| =
𝑛(𝑛+5)

2
. See Figure 5 (a) and 5 (b) for 

illustration.                                                                                                                                             ∎ 
 

Theorem 4. For 𝑛 ≥ 3, the local metric dimension of line graph of wheel is 𝐿𝐷𝑖𝑚(𝐿(𝑊𝑛)) = 𝑛−1. 

Proof. By observation 4, the order and the size of 𝐿(𝑊𝑛) are |𝑉(𝐿(𝑊𝑛))| = 2𝑛 and |𝐸(𝐿(𝑊𝑛))| =

𝑛(𝑛+5)

2
, respectively. Suppose the lower bound of 𝐿(𝑊𝑛)  is 𝑙𝑑𝑖𝑚(𝐿(𝑊𝑛)) ≥ 𝑛−2 with the resolving 

set 𝑊′ = {𝑥𝑖,1;1 ≤ 𝑖 ≤ 𝑛−2}. Thus two vertices of 𝑉(𝐿(𝑊𝑛))−𝑊
′ with respect to 𝑊′ are 

𝑟(𝑥𝑛−1,1|𝑊
′) = 𝑟(𝑥𝑛,1|𝑊

′) = ( 1,…,1⏟  
𝑛−2 𝑡𝑖𝑚𝑒𝑠

) 

It is easy to see that the line graph of wheel possess the same vertex representation respecting to 
𝑊′. Thus the lower bound is 𝑙𝑑𝑖𝑚(𝐿{𝑊𝑛}) ≥ 𝑛−1. Now, we will show that 𝑙𝑑𝑖𝑚(𝐿{𝑊𝑛}) ≤ 𝑛−1 



On The Local Metric Dimension of Line Graph of Special Graph 

Marsidi 129 

by determining the resolving set 𝑊 = {𝑥𝑖,1;1 ≤ 𝑖 ≤ 𝑛−1} and the vertex representation of 
𝑉(𝐿{𝑊𝑛})−𝑊 respect to 𝑊, as follows. 

𝑊 = {𝑥1,1,𝑥2,1,𝑥3,1,𝑥4,1,𝑥5,1,𝑥6,1,𝑥7,1} 

 

𝑟(𝑥𝑛,1|𝑊) = ( 1,…,1⏟  
𝑛−1 𝑡𝑖𝑚𝑒𝑠

) 

𝑟(𝑥𝑖,2|𝑊) = ( 2,…,2⏟  
𝑖−1 𝑡𝑖𝑚𝑒𝑠

,1, 2,…,2⏟  
𝑛−𝑖−1 𝑡𝑖𝑚𝑒𝑠

);2 ≤ 𝑖 ≤ 𝑛−1 

 

𝑟(𝑥1,2|𝑊) = (1,1, 2…,2⏟  
𝑛−3 𝑡𝑖𝑚𝑒𝑠

) 

𝑟(𝑥𝑛,2|𝑊) = (1, 2,…,2⏟  
𝑛−2 𝑡𝑖𝑚𝑒𝑠

) 

It easy to see that ∀𝑢,𝑣 ∈ 𝑉(𝐿(𝑊𝑛))−𝑊 have a different representation respect to 𝑊 for every 

pair 𝑢,𝑣 of adjacent vertices in 𝐿(𝑊𝑛). The cardinality of resolving set 𝐿(𝑊𝑛) is 𝑛−1, thus 
𝑙𝑑𝑖𝑚(𝐿(𝑊𝑛)) ≤ 𝑛−1. It concludes the proof.  See Figure 5 (c) for illustration.      ∎ 
 

 
Figure 5. (a) 𝑊8,  (b) 𝐿{𝑊8}, (c) Construction of local resolving set 

 

CONCLUSION 

We have shown the local metric dimension number of line graph of special graphs, namely line graph 

of path, cycle, star, and wheel. The results show that the local metric dimension numbers attain the best 

lower bound. However we have not found the sharpest lower bound for any connected graph, therefore 

we proposed the following open problem. 

 

Open Problem 1. Let 𝐺 be a connected graph, obtain the best lower bound of the local metric dimension 
of any graph 𝐺. 

 

  



On The Local Metric Dimension of Line Graph of Special Graph 

Marsidi 130 

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] M. Imran, A. Q. Baig, S. Ahtsham, U. Haq, and I. Javaid, “On the metric dimension of circulant 
graphs,” Appl. Math. Lett., vol. 25, no. 3, pp. 320–325, 2012. 

[4] G. A. B. Ramirez, C. G. Gomez, and J. A. R. Valazquez, “Closed formulae for the local metric 
dimension of corona product graphs,” Electron. notes Discret. Math., vol. 46, pp. 27–34, 2014. 

[5] LECTURE 1, “INTRODUCTION TO GRAPH MODELS,” pp. 1–25. 
[6] D. Garijo, A. González, and A. Márquez, “On the metric dimension , the upper dimension and the 

resolving number of graphs,” Discret. Appl. Math., vol. 161, no. 10–11, pp. 1440–1447, 2013. 
[7] H. Iswadi, E. T. Baskoro, A. N. M. Salman, R. Simanjuntak, N. Science, and U. Surabaya, “THE METRIC 

DIMENSION OF AMALGAMATION,” Far East J. Math. Sci., vol. 41, no. 1, pp. 19–31, 2010. 
[8] I. Javaid, M. T. Rahim, and K. Ali, “Families of regular graphs with constant metric dimension,” Util. 

Math., no. October 2016, 2008. 
[9] M. A. Chaudhry, I. Javaid, and M. Salman, “Fault-Tolerant Metric and Partition Dimension of 

Graphs,” Util. Math., 2010.