How to cite: A. Mardhaningsih, “A Note On The Partition Dimension of Thorn of Fan 

Graph”, mantik, vol. 5, no. 1, pp. 45-49, May 2019. 

A Note On The Partition Dimension of Thorn of Fan Graph 
 

 

Auli Mardhaningsih 

Andalas University, aulimardhaningsih@gmail.com 

 

doi: https://doi.org/10.15642/mantik.2019.5.1.45-49 

 

 
Abstrak: Misalkan G adalah suatu graf terhubung.Himpunan titikV(G) di partisi menjadi k buah 

partisi S1, S2,…, Sk yang saling lepas. Notasikan Π = {S1, S2, ..., Sk}.Maka representasi v ∈V(G) 

terhadap phi didefenisikan : r(v|Π)=(d(v,S1),d(v,S2),...,d(v,Sk)), Jika untuk setiap dua titik yang 

berbeda 𝑢, 𝑣 ∈ V(G) berlaku r(u|Π) = r(v|Π), maka Π dikatakan partisi penyelesaian dari graf G. 
Graf kipas diperoleh dari operasi graf hasil tambah K1+Pn. Graf kipas dinotasikan dengan 𝐹1,𝑛 
untuk n ≥ 2. Graf thorn untuk graf kipas diperoleh dengan cara menambahkan daun sebanyak 

li kesetiap titik di graf kipas, dinotasikan dengan 𝑇ℎ(𝐹1,𝑛, 𝑙1, 𝑙2, … , 𝑙𝑛+1). Pada tulisan ini, akan 
dibahas tentang dimensi partisi graf thorn dari graf kipas F1,nuntuk n = 2, 3,4. 

 

Kata kunci: Partisi penyelesaian, dimensi partisi, graf kipas, graf thorn 

 

 
Abstract: Let 𝐺 = (𝑉, 𝐸) be a connected graph and 𝑆 ⊆ 𝑉(𝐺). For a vertex 𝑣 ∈ 𝑉(𝐺) and an 
ordered k-partition Π = {𝑆1, 𝑆2, … , 𝑆𝑘 } of 𝑉(𝐺), the presentation of 𝑣 concerning Π is the k-vector 
𝑟(𝑣|Π) = (𝑑(𝑣, 𝑆1), 𝑑(𝑣, 𝑆2), … , 𝑑(𝑣, 𝑆𝑘 )), where 𝑑(𝑣, 𝑆𝑖 ) denotes the distance between 𝑣 and 𝑆𝑖  
for 𝑖 ∈ {1,2, … , 𝑛}. The k-partition Π is said to be resolving if for every two vertices 𝑢, 𝑣 ∈ 𝑉(𝐺), 
the representation 𝑟(𝑢|Π) ≠ 𝑟(𝑣|Π). The minimum k for which there is a resolving k-partition of 
𝑉(𝐺) is called the partition dimension of 𝐺, denoted by 𝑝𝑑(𝐺). Let 𝑉(𝐺) = {𝑥1, 𝑥2, … , 𝑥𝑛}. Let 
𝑙1, 𝑙2, … , 𝑙𝑛 be non-negative integer, 𝑙𝑖 ≥ 1,for 𝑖 ∈ {1,2, … , 𝑛}. The thorn of 𝐺, with parameters 
𝑙1, 𝑙2, … , 𝑙𝑛 is obtained by attaching 𝑙𝑖 vertices of degree one to the vertex 𝑥𝑖, denoted by 
𝑇ℎ(𝐺, 𝑙1, 𝑙2, … , 𝑙𝑛 ). In this paper, we determine the partition dimension of 𝑇ℎ(𝐺, 𝑙1, 𝑙2, … , 𝑙𝑛 )where 
𝐺 ≃  𝐹1,𝑛, the fan on n+1 vertices, for 𝑛 = 2,3,4. 
 

Keywords: Resolving partition, partition dimension, fan, thorn graph 

 

 
 

 

 

 

  

Jurnal Matematika MANTIK 

Vol. 5, No. 1, May 2019, pp. 45-49 

 

ISSN: 2527-3159 (print) 2527-3167 (online) 



Jurnal Matematika MANTIK 

Vol. 5, No. 1, May 2019, pp. 45-49 
 

46 

 

1. Introduction 

Let 𝐺 = (𝑉, 𝐸) be an arbitrary connected graph. [1] defined the partition dimension 
as follows. Let 𝑢 and 𝑣 be two vertices in 𝑉(𝐺). The distance 𝑑(𝑢, 𝑣) is the length of the 
shortest path between 𝑢 and 𝑣in 𝐺. For an ordered set Π = {𝑆1, 𝑆2, … , 𝑆𝑘} of vertices in a 
connected graph 𝐺 and a vertex 𝑣of 𝐺, the k-vector 𝑟(𝑣|Π) =
(𝑑(𝑣, 𝑆1), 𝑑(𝑣, 𝑆2), … , 𝑑(𝑣, 𝑆𝑘)), is the presentation of 𝑣 with respect to Π. The minimum 
k for which there is a resolving k-partition of 𝑉(𝐺) is called the partition dimension of 𝐺, 
denoted by 𝑝𝑑(𝐺). All notation in graph theory needed in this paper refers to [2]. 

Stated the following theorem. 

 

Theorem 1.1. [2] Let 𝐺 be a connected graph on n vertices, 𝑛 ≥ 2. Then 𝑝𝑑(𝐺) = 2 if 
and only if 𝐺 ≃ 𝑃𝑛. 

In the same paper, Chartrand et al. [2] also gave the necessary condition in 

partitioning the set of vertices as follows. 

 

Lemma 1.2. [2] Suppose that Π is the resolving partition of  𝑉(𝐺)and 𝑢, 𝑣 ∈ 𝑉(𝐺). If 
𝑑(𝑢, 𝑤) = 𝑑(𝑣, 𝑤)  for every vertex 𝑤 ∈ 𝑉(𝐺)\{𝑢, 𝑣}  then 𝑢 and 𝑣 belong to a different 
class of  Π. 
 

2. Main Results 

The fan 𝐹1,𝑛 on 𝑛 + 1 vertices is defined as the graph constructed by joining 𝐾1 and 

𝑃𝑛, denoted by 𝐾1 + 𝑃𝑛 where 𝐾1 is the complete graph on 1 vertex and 𝑃𝑛 Is a path on 𝑛 
vertices, for 𝑛 ≥ 2. The vertex set and edge set of  𝐹1,𝑛 are as follows.  

 

 𝑉(𝐹1,𝑛) = {𝑥𝑖 |1 ≤ 𝑖 ≤ 𝑛 + 1}, 

 𝐸(𝐹1,𝑛) = {𝑥1𝑥𝑡 |1 ≤ 𝑡 ≤ 𝑛}  ∪ {𝑥𝑠 𝑥𝑠+1|1 ≤ 𝑠 ≤ 𝑛 − 1}. 
 

𝑙1, 𝑙2, … , 𝑙𝑛+1Be some positive integer. The thorn graph of 𝐹1,𝑛 is obtained by adding 𝑙𝑖  

leaves to vertex 𝑥𝑖 , for 1 ≤ 𝑖 ≤ 𝑛 + 1, denoted by 𝑇ℎ(𝐹1,𝑛, 𝑙1, 𝑙2, … , 𝑙𝑛+1). The 

construction of thorn graph is taken from [3]. The vertex set and edge set of 𝐻 ≃

𝑇ℎ(𝐹1,𝑛, 𝑙1, 𝑙2, … , 𝑙𝑛+1) are as follows. 

 

 𝑉(𝐻) = {𝑥𝑖 |1 ≤ 𝑖 ≤ 𝑛 + 1} ∪ {𝑥𝑖𝑗 |1 ≤ 𝑖 ≤ 𝑛 + 1, 1 ≤ 𝑗 ≤ 𝑙𝑖 }, and 

 𝐸(𝐻) = {𝑥1𝑥𝑡 |1 ≤ 𝑡 ≤ 𝑛}  ∪ {𝑥𝑠 𝑥𝑠+1|1 ≤ 𝑠 ≤ 𝑛 − 1} ∪

{𝑥𝑖 𝑥𝑖𝑗 |1 ≤ 𝑖 ≤ 𝑛, 1 ≤ 𝑗 ≤ 𝑛}. 

 

In Theorem 2.1 we determine the partition dimension of  𝑇ℎ(𝐹1,2, 𝑙1, 𝑙2, 𝑙3)for 𝑙𝑖 ≥ 1,

𝑖 ∈ 1,2,3. 
 

Theorem 2.1. Let 𝑇ℎ(𝐹1,2, 𝑙1, 𝑙2, 𝑙3) be thorn of fan 𝐹1,2with 𝑙𝑖 ≥ 1, 𝑖 ∈ 1,2,3. Denote 

𝑙𝑚𝑎𝑥 = max {𝑙1, 𝑙2, 𝑙3}. 

The partition dimension of  𝑇ℎ(𝐹1,2, 𝑙1, 𝑙2, 𝑙3) is 
 

𝑝𝑑(𝑇ℎ(𝐹1,2, 𝑙1, 𝑙2, 𝑙3)) = {
3,   𝑓𝑜𝑟 𝑙𝑚𝑎𝑥 = 1, 2 𝑜𝑟 3

𝑙𝑚𝑎𝑥 , 𝑓𝑜𝑟 𝑙𝑚𝑎𝑥 ≥ 4        
 

 



A. Mardhaningsih 
A Note On The Partition Dimension of Thorn of Fan Graph 

47 

 

 
 

Figure 1. 𝑇ℎ(𝐹1,2, 𝑙1, 𝑙2, 𝑙3) 

 

Proof. The proof is divided into two cases. 

 

Case 1. 1 ≤ 𝑙𝑚𝑎𝑥 ≤ 3. 

Let 𝐻1 ≃ 𝑇ℎ(𝐹1,2, 𝑙1, 𝑙2, 𝑙3), with 1 ≤ 𝑙𝑚𝑎𝑥 ≤ 3. Because 𝐻1 ≠ 𝑃𝑛 then from Theorem 

1.1, it is obtained that 𝑝𝑑(𝐻1) ≥ 3. Next, it will be shown that 𝑝𝑑(𝐻1) ≤ 3 by 
constructing three ordered partitions. Note that from Lemma 1.2, every leaf at the vertex 

𝑥𝑖  Must be on a different partition. Therefore, we define Π = {𝑆1, 𝑆2, 𝑆3}, where 
𝑆𝑖 = {𝑥𝑖 , 𝑥𝑘𝑖 |1 ≤ 𝑖 ≤ 3, 1 ≤ 𝑘 ≤ 3}, 
Because of 𝑑(𝑣, 𝑆𝑖) = 0 while 𝑑(𝑢, 𝑆𝑖) ≠ 0 for 𝑣 ∈ 𝑆𝑖 and 𝑢 ∉ 𝑆𝑖 , it is clear that every 
two vertices in different partitions have different representations. Therefore, it is 

sufficient to check the representations of two vertices in the same partition. Because of 

𝑑(𝑥𝑘𝑖 , 𝑆𝑗 ) = 𝑑(𝑥𝑖 , 𝑆𝑗 ) + 1for 𝑖 ≠ 𝑗, 1 ≤ 𝑖, 𝑗 ≤ 3, then 𝑟(𝑥𝑘𝑖 |Π) ≠ 𝑟(𝑥𝑖 |Π). Thus, we 

have that 𝑝𝑑(𝐻1) ≤ 3. 
 

Case 2. 𝑙𝑚𝑎𝑥 ≥ 4. 

Let 𝐻2 ≃ 𝑇ℎ(𝐹1,2, 𝑙1, 𝑙2, 𝑙3), with 𝑙𝑚𝑎𝑥 ≥ 4. Let 𝑙𝑚𝑎𝑥 = 𝑚 and suppose that 𝑝𝑑(𝐻2) =

𝑚 − 1. Then we have Π = {𝑆1, 𝑆2, … , 𝑆𝑚−1}. Thus there are at least two vertices, namely 
𝑥1𝑝 and 𝑥1𝑞 , in the same partition, for 1 ≤ 𝑝, 𝑞 ≤ 𝑚. But from Lemma 1.2, 𝑥1𝑝  and 𝑥1𝑞  

Must be placed in different partitions. Therefore, |Π| ≥ 𝑚, a contradiction. 
Next, we construct Π = {𝑆1, 𝑆2, … , 𝑆𝑚}, where 

𝑆𝑖 = {𝑥𝑖 , 𝑥𝑘𝑖 |1 ≤ 𝑖 ≤ 3, 1 ≤ 𝑘 ≤ 3}, 

𝑆𝑗 = {𝑥𝑘𝑗 |1 ≤ 𝑘 ≤ 3, 4 ≤ 𝑗 ≤ 𝑙𝑚𝑎𝑥 }, 

Because of 𝑑(𝑥𝑘𝑖 , 𝑆𝑗 ) = 𝑑(𝑥𝑖 , 𝑆𝑗 ) + 1for 𝑖 ≠ 𝑗, 1 ≤ 𝑖, 𝑗 ≤ 𝑙𝑚𝑎𝑥 , then 𝑟(𝑥𝑘𝑖 |Π) ≠

𝑟(𝑥𝑖 |Π). Next, because of 𝑑(𝑥𝑘𝑖 , 𝑆𝑗 ) ≠ 𝑑(𝑥𝑙𝑖 , 𝑆𝑗 ) + 1for 𝑘 ≠ 𝑙, 1 ≤ 𝑘, 𝑙 ≤ 𝑙𝑚𝑎𝑥 , it is 

clear that 𝑟(𝑥𝑘𝑖 |Π) ≠ 𝑟(𝑥𝑙𝑖 |Π). Therefore, we have 𝑝𝑑(𝐻2) ≤ 𝑙𝑚𝑎𝑥 . ∎   
     

In Theorem 2.2 we determine the partition dimension of  𝑇ℎ(𝐹1,3, 𝑙1, 𝑙2, 𝑙3, 𝑙4)for 𝑙𝑖 ≥

1, 𝑖 ∈ 1,2,3,4. 
 

Theorem 2.2. Let 𝑇ℎ(𝐹1,3, 𝑙1, 𝑙2, 𝑙3, 𝑙4) be a thorn of fan 𝐹1,3with 𝑙𝑖 ≥ 1, 𝑖 ∈ 1,2,3,4. 

Denote 𝑙𝑚𝑎𝑥 = max {𝑙1, 𝑙2, 𝑙3, 𝑙4}. Let 𝑥𝑙𝑖  be the vertex in 𝐹1,3 with 𝑙𝑖  leaves, and  |𝑥𝑙𝑚𝑎𝑥 | 

be the number of vertices with 𝑙𝑚𝑎𝑥  Leaves. The partition dimension of  

𝑇ℎ(𝐹1,3, 𝑙1, 𝑙2, 𝑙3, 𝑙4) is 



Jurnal Matematika MANTIK 

Vol. 5, No. 1, May 2019, pp. 45-49 
 

48 

 

 
 

 

Figure2. 𝑇ℎ(𝐹1,3, 𝑙1, 𝑙2, 𝑙3, 𝑙4) 

 

Proof. The proof is similar to the proof of Theorem 2.1    ∎ 
 

In Theorem 2.3 we determine the partition dimension of  𝑇ℎ(𝐹1,4, 𝑙1, 𝑙2, 𝑙3, 𝑙4, 𝑙5)for 

𝑙𝑖 ≥ 1, 𝑖 ∈ 1,2,3,4,5. 
 

Theorem 2.3. Let 𝑇ℎ(𝐹1,4, 𝑙1, 𝑙2, 𝑙3, 𝑙4, 𝑙5) be a thorn of fan 𝐹1,4with 𝑙𝑖 ≥ 1, 𝑖 ∈ 1,2,3,4,5. 

Denote 𝑙𝑚𝑎𝑥 = max  {𝑙1, 𝑙2, 𝑙3, 𝑙4, 𝑙5}. Let 𝑥𝑙𝑖  be the vertex in 𝐹1,4 with 𝑙𝑖  leaves, and  

|𝑥𝑙𝑚𝑎𝑥 | be the number of vertices with 𝑙𝑚𝑎𝑥  Leaves. The partition dimension of  

𝑇ℎ(𝐹1,3, 𝑙1, 𝑙2, 𝑙3, 𝑙4, 𝑙5) is 
 

 



A. Mardhaningsih 
A Note On The Partition Dimension of Thorn of Fan Graph 

49 

 

 
 

Figure 3. 𝑇ℎ(𝐹1,4, 𝑙1, 𝑙2, 𝑙3, 𝑙4, 𝑙5) 
 

 

Proof. The proof is similar to the proof of Theorem 2.1 and Theorem 2.2.    

 

References 

 

[1]  G. Chartrand, S. E and Z. P, "The Partition dimension of a graph," Aequationes 
Math, pp. 45-54, 2000.  

[2]  J. A. Bondy and U. Murty, Graph Theory with Applications, London, 1976.  

[3]  A. "Partition dimension of amalgamation," Bulletin of Mathematics, pp. 161-167, 
2012.  

[4]  A. Kirlangic, "The Scattering number of thorn graph," International Journal of 
computer math, pp. 299-311, 2004.  

[5]  E. Baskoro and D. , "The partition dimension of corona product of two graph," Far 
East J. Math. Sci, pp. 181-196, 2012.  

[6]  N. L. Biggs, R. Lloyd and R. Wilson, Graph theory, Oxford: 1736-1936, 1986.  

[7]  G. Chartrand and S. E, "On partition dimension of a graph," Congr. numer, pp. 157-
168, 1998.  

[8]  E. Rahimah, L. Yulianti and D. Welyyanti, "Penentuan bilangan kromatik lokasi graf 
thorn dari graf roda," jurnal matematika unand, 2018.  

[9]  J. Gross and J. Yellen, Graph theory and its applications (Second Edition), New 
York, 2006.  

[10]  I. Gutman, "Distance in Thorny Graph," Publ.Ins.Math, pp. 31-36, 1998.  

[11]  D. O. Haryeni, E. T. Baskoro, and S. W. Saputro, "On the partition dimension of 
disconnected graphs," 2017.  

[12]  A. Juan, V. Rodriguez and L. Magdalena, "On the partition dimension of trees," 
discrete applied mathematics, pp. 204-209, 2014.  

[13]  E. Lloyd, J. Bondy and U. Murt, "Graph theory with apllication," the mathematical 
gazette, pp. 62-63, 2007.  

[14]  R. Munir, Matematika Diskrit, Bandung, 2003.  

[15]  I. Tomescu, I. Javaid and S. , "On the Partition Dimension and Conected Partition 
dimension of wheels," Ars Combinatoria, pp. 311-317, 2007.  

[16]  I. Tomescu, "Discrepancies between metric dimension of a connected graph," 
Discrete Math, pp. 5026-5031, 2008.