On 2-partition dimension of the circulant graphs

Abstract

The partition dimension is a variant of metric dimension in graphs. It has arising applications in the fields of network designing, robot navigation, pattern recognition and image processing. Let G (V (G) , E (G)) be a connected graph and Γ = {P₁, P₂, …, P_m} be an ordered m-partition of V (G). The partition representation of vertex v with respect to Γ is an m-vector r (v|Γ) = (d (v, P₁) , d (v, P₂) , …, d (v, P_m)), where d (v, P) = min {d (v, x) |x ∈ P} is the distance between v and P. If the m-vectors r (v|Γ) differ in at least 2 positions for all v ∈ V (G), then the m-partition is called a 2-partition generator of G. A 2-partition generator of G with minimum cardinality is called a 2-partition basis of G and its cardinality is known as the 2-partition dimension of G. Circulant graphs outperform other network topologies due to their low message delay, high connectivity and survivability, therefore are widely used in telecommunication networks, computer networks, parallel processing systems and social networks. In this paper, we computed partition dimension of circulant graphs C_n (1, 2) for n ≡ 2 (mod 4), n ≥ 18 and hence corrected the result given by Salman et al. [Acta Math. Sin. Engl. Ser. 2012, 28, 1851-1864]. We further computed the 2-partition dimension of C_n (1, 2) for n ≥ 6.

Keywords

Network topology design Circulant graphs partition dimension

1 Introduction and preliminaries

Ever growing telecommunication networks sizes make it difficult to get an exact map of worldwide network so local measurements are made on smaller subsets of networks to evaluate the actual network and hence optimize the computational cost. A subset of nodes with smallest cardinality such that each node in the network is at a unique distance from the nodes in the subset helps us to identify the whole network. The process is same as computing the metric dimension of the graph and its generalized version called the partition dimension. A network topology is the graphic description of a network, connecting various nodes through lines of connection. Network topology designs play a key role in network planning. Circulant graphs outperform other network topologies due to their low message delay, high connectivity and survivability, therefore are widely used in telecommunication networks, computer networks, parallel processing systems and social networks [8 , 35]. Furthermore, the applications of fuzzy graphs and graph labeling can be seen in computer science, decision making, telecommunication networks, parallel processing and social networks related problems (see [2–6 , 49]).

Slater and Melter et al. presented the notion of metric dimension of graphs independently in [46] and [23] respectively. Its application can be seen in robotics [30], chemistry [10] and optimization [44]. In [12], Chartrand et al. introduced a variant of metric dimension of graph which is called partition dimension of graph. In [19], Garey et al. proved that the computation of metric dimension is an NP-hard problem which implies that the problem of finding the partition dimension is also NP-hard.

Consider a connected graph G of order n with the vertex set V (G) and edge set E (G). If all the vertices of a graph have degree r, where 0 ≤ r ≤ n - 1, then it is known as a r-regular graph. The distance d (u, v) between the vertices is the length of a shortest path connecting the two vertices u, v ∈ V (G). The distance between a vertex v and a subset P of V (G) is d (v, P) = min {d (v, x) |x ∈ P} and neighborhood of v in G is N (v) = {u ∈ V (G) |uv ∈ E (G)}. For an ordered set Ω = {v₁, v₂, …, v_m} of vertices, the representation of a vertex v with respect to Ω is an m-vector r (v|Ω) = (d (v, v₁) , d (v, v₂) , …, d (v, v_m)). If the m-vectors r (v|Ω) are distinct, for all v ∈ V (G), then Ω is called a resolving set of G. The minimum value of m for which there is a resolving set is called the metric dimension of G, denoted by dim (G). Let Γ = {P₁, P₂, …, P_m} be an ordered m-partition of the vertex set of a connected graph G. The partition representation of vertex v with respect to Γ is an m-vector r (v|Γ) = (d (v, P₁) , d (v, P₂) , …, d (v, P_m)). If the m-vectors r (v|Γ) are distinct, for all v ∈ V (G), then m-partition is called a resolving partition of G. The minimum value of m for which there is a resolving m-partition is called the partition dimension of G, denoted by pd (G). In [12], Chartrand et al. compared metric dimension and partition dimension of graphs and also characterized all the graphs with partition dimension 2 or n. The following results are important for us.

Proposition 1.1. [12] Let G be a connected graph of order n then

pd (G) ≤ dim(G) +1;

pd (G) =2 if and only if G = P_n where P_n is a path of order n ≥ 2;

pd (G) = n if and only if G = K_n where K_n is the complete graph.

In [13], Dewi et al. calculated the partition dimension of the lollipop graph and the Jahangir graph. In [18], Fredlina et al. computed the partition dimension of homogeneous caterpillars and homogeneous banana trees. In [17], Fernau et al. discussed the partition dimension of unicyclic graphs. The partition dimension of fullerene graphs, cycle books graph and nanotubes has been studied in [34], [43] and [45] respectively. For more results and discussion on partition dimension of graphs, we refer to articles [1 , 26].

In [16], Estrado - Moreno et al. generalized the notion of metric dimension to k-metric dimension which is defined as follows: Let Ω = {v₁, v₂, …, v_m} be an ordered set of vertices, the representation of a vertex v with respect to Ω is an m-vector r (v|Ω) = (d (v, v₁) , d (v, v₂) , …, d (v, v_m)). If the m-vectors r (v|Ω) differ in at least k coordinates for all v ∈ V (G), then Ω is called a k-metric generator for G. A metric generator of minimum cardinality is called a k-metric basis and its cardinality the k-metric dimension of G, denoted by dim_k (G). For k = 1, it is metric dimension of G and for k = 2, it is known as fault tolerant metric dimension of G. The fault tolerant dimension of a graph was first introduced by Hernando et al. in [25]. For more results and discussion on k-metric dimension, we refer to articles [29 , 47].

In [15], Estrado - Moreno further generalized the notion of partition dimension of graph to k-partition dimension of graph. Let Γ = {P₁, P₂, …, P_m} be an ordered m-partition of V (G). The partition representation of vertex v with respect to Γ is an m-vector r (v|Γ) = (d (v, P₁) , d (v, P₂) , …, d (v, P_m)). If the m-vectors r (v|Γ) differ in at least k coordinates for all v ∈ V (G), then Γ is called a k-partition generator of G. A partition generator of minimum cardinality is called a k-partition basis and its cardinality the k-partition dimension of G, denoted by pd_k (G). For k = 2, 2-partition dimension for certain classes of graphs have been discussed in [7] and [11]. For u, v ∈ V (G), let D_G (u, v) = {w ∈ G : d (w, u) ≠ d (w, v)} and $ϒ (G) = min_{u, v \in V (G)} {| D_{G} (u, v) |}$ .

Proposition 1.2. [15] Let G be a nontrivial connected graph of order n and let k₁, k₂ be two integers. If 1 < k₁ < k₂ ≤ ϒ (G), then k₁ ≤ pd_{k
₁} (G) ≤ pd_{k
₂} (G) ≤ n. Moreover, 2 ≤ pd (G) ≤ n.

Proposition 1.3. [15] If G is a connected graph of order n ≥ 2, then for k ∈ {1, 2, …, ϒ (G) -1}, pd_k (G) ≤ dim_k (G) +1.

Proposition 1.4. [15] If P_n is a path of order n ≥ 3, then pd_k (P_n) = k + 1 for any k ∈ {1, 2, …, n - 1}.

In this paper, we discuss the special class of circulant graphs C_n (1, 2, …, t) which consists of vertices v₀, v₁, …, v_n-1 and the connection set {1, 2, …, t} for 1≤ t ≤ ⌊ n/2 ⌋. The circulant graph C_n (1, 2, …, t) is formed by cyclically arranging the vertices in such a way that, for (0 ≤ i ≤ n - 1), join v_i to v_i+k and v_i-k, where 1 ≤ k ≤ t. The graph C₆ (1, 2) is shown in Figure 1. For v_i and v_j in the vertex set of C_n (1, 2, …, t), where 0 ≤ i < j < n, d (v_i, v_j) is defined in [33] as follows:

Fig. 1

The circulant graph C₆ (1, 2).

$d (v_{i}, v_{j}) = {\begin{matrix} ⌈ \frac{j - i}{t} ⌉, & if 0 \leq j - i \leq \frac{n}{2}; \\ ⌈ \frac{n - (j - i)}{t} ⌉, & if \frac{n}{2} < j - i < n . \end{matrix}$

The discussion on metric dimension of circulant graphs can be seen in [20 , 42].

The rest of the paper is structured as follows. In Section 2, we give known results of circulant graphs and compute the partition dimension of circulant graphs C_n (1, 2). In Section 3, we compute the 2-partition dimension of circulant graphs C_n (1, 2).

2 Partition dimension of circulant graphs C_n (1, 2)

In this section, partition dimension is discussed for circulant graphs C_n (1, 2). Many authors have discussed the partition dimension of circulant graphs in [21 , 42]. Javaid et al. in [28] discussed the partition of circulant graphs with connection sets {1, 3} and {1, 4}. Salman et al. in [42] proved the following theorem.

Theorem 2.1. [42] Consider C_n (1, 2) then $pd (C_{n} (1, 2)) = {\begin{matrix} 3, & if n is odd and n \geq 9; \\ 4, & if n is even and n \geq 6 or n = 7 . \end{matrix}$

Grigorious et al. in [22] disproved the claims in Theorem 2 for n ≡ 0 (mod 4) and n ≥ 12. Their result is stated in Theorem 2.

Theorem 2.2. [22] Let n ≡ 0 (mod 4) and n ≥ 12. Then pd (C_n (1, 2)) =3.

In the following theorem, we computed the partition dimension of C_n (1, 2) for n ≡ 2 (mod 4) and n ≥ 18 and hence corrected the result given in Theorem 2.

Theorem 2.3. Let n ≡ 2 (mod 4) and n ≥ 18. Then pd (C_n (1, 2)) =3.

Proof. For our convenience we take v₀ = v_n. To prove that pd (C_n (1, 2)) ≤3, we give a resolving partition, Γ = {P₁, P₂, P₃} of V (C_n (1, 2)). Let n = 4α + 2. If α ≥ 4, then, P₁ = {v_t|1 ≤ t ≤ 4α - 7} ∪ {v_4α-5, v_4α-2, v_4α+1}, P₂ = {v_4α-6, v_4α-4, v_4α-3} and P₃ = {v_4α-1, v_4α, v_4α+2}. The partition representations of all the vertices of C_n (1, 2) are given in Table 1.

Table 1
Partition representations of the vertices for C_n (1, 2)

Representation of v_t d (v_t, P₁) d (v_t, P₂) d (v_t, P₃)

v_2s+1 (0 ≤ s ≤ α - 3) 0 s + 3 s + 1

v_2s+2 (0 ≤ s ≤ α - 4) 0 s + 4 s + 1

v _2α-4 0 α - 1 α - 2

v _2α-3 0 α - 1 α - 1

v _2α-2 0 α - 2 α - 1

v_4α-2s-3 (2 ≤ s ≤ α - 1) 0 s - 1 s + 1

v_4α-2s (4 ≤ s ≤ α) 0 s - 3 s

v _4α-5 0 1 2

v _4α-2 0 1 1

v _4α+1 0 2 1

v _4α-6 1 0 3

v _4α-4 1 0 2

v _4α-3 1 0 1

v _4α-1 1 1 0

v _4α 1 2 0

v _4α+2 1 3 0

Representation of v_t	d (v_t, P₁)	d (v_t, P₂)	d (v_t, P₃)
v_2s+1 (0 ≤ s ≤ α - 3)	0	s + 3	s + 1
v_2s+2 (0 ≤ s ≤ α - 4)	0	s + 4	s + 1
v _2α-4	0	α - 1	α - 2
v _2α-3	0	α - 1	α - 1
v _2α-2	0	α - 2	α - 1
v_4α-2s-3 (2 ≤ s ≤ α - 1)	0	s - 1	s + 1
v_4α-2s (4 ≤ s ≤ α)	0	s - 3	s
v _4α-5	0	1	2
v _4α-2	0	1	1
v _4α+1	0	2	1
v _4α-6	1	0	3
v _4α-4	1	0	2
v _4α-3	1	0	1
v _4α-1	1	1	0
v _4α	1	2	0
v _4α+2	1	3	0

It is easy to check that all the partition representations are distinct. This shows that pd (C_n (1, 2)) ≤3 for n ≡ 2 (mod 4) and n ≥ 18. Since C_n (1, 2) is not a path so Proposition 1 implies that pd (C_n (1, 2)) ≥3 for n ≡ 2 (mod 4) and n ≥ 18, which completes the proof.■

Finally, we conclude the above discussion for the partition dimension of C_n (1, 2) in the following theorem for n ≥ 6.

Theorem 2.4. Consider C_n (1, 2) for n ≥ 6 then $pd (C_{n} (1, 2)) = {\begin{matrix} 4, & when n \in {6, 7, 8, 10, 14}; \\ 3, & otherwise . \end{matrix}$

3 2-partition dimension of circulant graphs C_n (1, 2)

The partition dimension of circulant graphs C_n (1, 2) has been discussed by Salman et al. in [42] and by Grigorious et al. in [22]. In this section firstly, we will prove that the upper bound of pd₂ (C_n (1, 2)) is 4 and elaborate it with an example. Secondly, we will compute the 2-partition dimension of the circulant graphs C_n (1, 2) for n ≠ 11. Finally, it will be shown that the pd₂ (C₁₁ (1, 2)) is 5.

Lemma 3.1. Let C_n (1, 2) be the circulant graph, then pd₂ (C_n (1, 2)) ≥4 for n ≥ 6.

Proof. Assume that pd₂ (C_n (1, 2)) =3. Let Γ = {P₁, P₂, P₃} be a 2-partition basis of C_n (1, 2). Clearly, one of the sets P₁, P₂ and P₃ contains at least two vertices. We can assume that |P₁|≥2. Note that at least one vertex, say v_t, has a coordinate of r (v_t|Γ) >1 otherwise, all the vertices in P₁ will have the r (v|Γ) = (0, 1, 1). So without loss of generality, we can assume that the third coordinate of r (v_t|Γ) is greater than 1. i.e. d (v_t, P₃) ≥2. Let v_j be a vertex in P₃ such that d (v_t, v_j) = d (v_t, P₃). Since C_n (1, 2) is 4-regular graph so |N (v_t) |=4. Let N (v_t) = {u₁, u₂, u₃, u₄} be the neighborhood of v_t. Therefore, we have N (v_t)∩ P₃ = ∅, since d (u, v_t) < d (v_t, v_j) for all u ∈ N (v_t).

All the vertices of N (v_t) are in the same set P₁ or P₂.

Assume that N (v_t) ⊆ P₁, then

r (v_t|Γ) = (0, a₀, b₀) and for u_j ∈ N (v_t), r (u_j|Γ) = (0, a_j, b_j). Hence, a₀ - 1 ≤ a₁, a₂, a₃, a₄ ≤ a₀ + 1. So by Pigeonhole principle at least two of the vertices v_t and u_j will have the same distances from P₁ and P₂. This leads to a contradiction.

Assume that N (v_t) ⊆ P₂, then

r (v_t|Γ) = (0, 1, b₀) and for u_j ∈ N (v_t),

r (u_j|Γ) = (1, 0, b_j). This clearly shows that the partition representations are not distinct at two places.

If three vertices from the set N (v_t) are in P₁ or P₂.

Let u_p, u_q, u_r ∈ N (v_t) ∩ P₁ and

u_t ∈ N (v_t) ∩ P₂ then

r (v_t|Γ) = (0, 1, b₀), r (u_p|Γ) = (0, a₁, b₁),

r (u_q|Γ) = (0, a₂, b₂) and r (u_r|Γ) = (0, a₃, b₃) In this case we have, 1 ≤ a₁, a₂, a₃ ≤ 2. Again by Pigeonhole principle at least two of the vertices v_t, u_p, u_q and u_r will have the same distances from P₁ and P₂. This leads to a contradiction.

Assume that u_p ∈ N (v_t) ∩ P₁ and u_q, u_r, u_t ∈ N (v_t) ∩ P₂ then

r (v_t|Γ) = (0, 1, b₀) , r (u_p|Γ) = (0, a₁, b₁),

r (u_q|Γ) = (1, 0, b₂) , r (u_r|Γ) = (1, 0, b₃) and r (u_t|Γ) = (1, 0, b₄). Clearly representations of u_q, u_r and u_t are same at two places. This leads to a contradiction.

If two vertices from the set N (v_t) are in P₁ and two in P₂.

Let u_p, u_q ∈ N (v_t) ∩ P₁ and u_r, u_t ∈ N (v_t) ∩ P₂ then r (v_t|Γ) = (0, 1, b₀) , r (u_p|Γ) = (0, a₁, b₁),

r (u_q|Γ) = (0, a₂, b₂) , r (u_r|Γ) = (1, 0, b₃) and r (u_t|Γ) = (1, 0, b₄). Clearly representations of u_r and u_t are same at two places. This leads to a contradiction. Hence, pd₂ (C_n (1, 2)) ≥4 for n ≥ 6.■

The following example is presented in support of the above result.

Example 3.2.

Consider a circulant graph C₆ (1, 2), shown in Figure 1. Let Γ = {P₁, P₂, P₃, P₄} be a partition of V (C₆ (1, 2)), where, P₁ = {v₁, v₃, v₅} , P₂ = {v₂}, P₃ = {v₄} and P₄ = {v₆}. Then the representations of vertices with respect to Γ are: r (v₁|Γ) = (0, 1, 2, 1), r (v₂|Γ) = (1, 0, 1, 1), r (v₃|Γ) = (0, 1, 1, 2), r (v₄|Γ) = (1, 1, 0, 1), r (v₅|Γ) = (0, 2, 1, 1) and r (v₆|Γ) = (1, 1, 1, 0). It can easily be seen from the partition representations of vertices of C₆ (1, 2), that Γ is a 2-partition generator.

In the following theorem, we compute the pd₂ (C_n (1, 2)) for n ≥ 6 and n ≠ 11.

Theorem 3.3. The pd₂ (C_n (1, 2)) =4 for n ≥ 6 and n ≠ 11.

Proof. Let Γ = {P₁, P₂, P₃, P₄} be a partition of V (C_n (1, 2)). The proof is divided into six cases and in each case we will show that Γ is the 2-partition generator of C_n (1, 2). For our convenience we take v₀ = v_n.

(For n = 6α and α ≥ 1).

Let P₁ = {v₁, v₃, …, v_6α-1} , P₂ = {v₂, v₄, …, v_2α}, P₃ = {v_2α+2, v_2α+4, …, v_4α} and

P₄ = {v_4α+2, v_4α+4, …, v_6α}.

The r (v_t|Γ) are given in Table 2.

(For n = 6α + 1 and α ≥ 1).

Let P₁ = {v₁, v₃, …, v_6α-1} , P₂ = {v₂, v₄, …, v_2α},

P₃ = {v_2α+2, v_2α+4, …, v_4α} and

P₄ = {v_4α+2, v_4α+4, …, v_6α, v_6α+1}.

The r (v_t|Γ) are given in Table 3.

(For n = 6α + 2 and α ≥ 1).

Let P₁ = {v₁, v₃, …, v_6α-3, v_6α},

P₂ = {v_4α, v_4α+2, …, v_6α-2, v_6α-1},

P₃ = {v₂, v₄, …, v_2(α-1), v_6α+1, v_6α+2} and P₄ = {v_2α, v_2α+2, …, v_4α-2)}.

The r (v_t|Γ) are given in Table 4.

(For n = 6α + 3 and α ≥ 1).

Let P₁ = {v₁, v₂, v₃, v₆, v₈, …, v_2α, v_2α+2,

v_2α+3, v_2α+4, v_2α+7, v_2α+9, …v_4α+1,

v_4α+3, v_4α+4, v_4α+5, v_4α+8, v_4α+10, …,

v_6α+2},

P₂ = {v₄, v₅, v₇, …, v_2α+1},

P₃ = {v_2α+5, v_2α+6, v_2α+8 … , v_4α+2} and P₄ = {v_4α+6, v_4α+7, v_4α+9, …, v_6α+3} The r (v_t|Γ) are given in Table 5.

(For n = 6α + 4 and α ≥ 1). The partition Γ for α ∈ {1, 2, 3, 4, 5} are given in Table 6 which clearly proves that Γ is the 2-partition generator.

For α ≥ 6, we have the following sub-cases:

(For n = 16 + 24p and p ≥ 1)

Let P₁ = {v₁, v₂, v₃, v₅, v₇, …, v_6p+5, v_n-6p-1, v_n-6p+1, …, v_n-1},

$P_{2} = {v_{4}, v_{6}, v_{8}, \dots, v_{\frac{n}{2}}}, P_{3} = {v_{6 p + 7}, v_{6 p + 9}$ , …, v_12p+7, v_12p+9, v_12p+10, v_12p+11, v_12p+13, v_12p+15, …, v_18p+13} and P₄ = {v_12p+12, v_12p+14, …, v_n}. The r (v_t|Γ) are given in Table 7.

(For n = 22 + 24p and p ≥ 1)

Let P₁ = {v₁, v₂, v₃, v₅, v₇, …, v_6p+5,

v_n-6p-3, v_n-6p-1, …, v_n-1},

P₂ = {v₄, v₆, v₈, …, v_6p+4, v_6p+6, v_6p+7,

v_6p+8, v_6p+10, v_6p+12, …, v_12p+10},

P₃ = {v_6p+9, v_6p+11, …, v_12p+9, v_12p+11, v_12p+12, v_12p+13, v_12p+15, v_12p+17, …, v_n-6p-5} and P₄ = {v_12p+14, v_12p+16, …, v_n}. The r (v_t|Γ) are given in Table 8.

(For n = 28 + 24p and p ≥ 1)

Let P₁ = {v₁, v₂, v₃, v₅, v₇, …, v_6p+7, v_n-6p-3, v_n-6p-1, …, v_n-1},

P₂ = {v₄, v₆, …, v_6p+6, v_6p+8, v_6p+9, $v_{6 p + 10}, v_{6 p + 12}, v_{6 p + 14}, \dots, v_{\frac{n}{2}}}$ ,

P₃ = {v_6p+11, v_6p+13, …, v_12p+13, v_12p+15, v_12p+16, v_12p+17, v_12p+19, v_12p+21, …, v_18p+21} and

P₄ = {v_12p+18, v_12p+20, …, v_18p+20, v_18p+22, v_18p+23, v_18p+24, v_18p+26, v_18p+28, …, v_n}.

The r (v_t|Γ) are given in Table 9.

(For n = 34 + 24p and p ≥ 1)

Let P₁ = {v₁, v₂, v₃, v₅, v₇, …, v_6p+9, v_n-6p-5, v_n-6p-3, …, v_n-1},

$P_{2} = {v_{4}, v_{6}, \dots, v_{\frac{n + 2}{2}}}$ ,

P₃ = {v_6p+11, v_6p+13, …, v_34p+11} and

$P_{4} = {v_{\frac{n + 2}{2} + 2}, v_{\frac{n + 2}{2} + 4}, \dots, v_{n}}$ .

The r (v_t|Γ) are given in Table 10.

(For n = 6α + 5 and α ≥ 2).

Let P₁ = {v₁, v₂, v₃, v₆, v₈, …, v_2α+4,

v_2α+7, v_2α+9, …, v_4α+3, v_4α+5, v_4α+6,

v_4α+7, v_4α+10, v_4α+12, …, v_6α+4},

P₂ = {v₄, v₅, v₇, …, v_2α+3},

P₃ = {v_2α+5, v_2α+6, v_2α+8, …, v_4α+4} and

P₄ = {v_4α+8, v_4α+9, v_4α+11, …, v_6α+5}.

The r (v_t|Γ) are given in Table 11.

It is clear from Table 2-11 that Γ is a 2-resolving generator of C_n (1, 2) for n ≥ 6, n ≠ 11, therefore, pd₂ (C_n (1, 2)) ≤4 for n ≥ 6, n ≠ 11. Lemma 3 implies that pd₂ (C_n (1, 2)) ≥4 for n ≥ 6. This establishes our claim.■

Table 2
Representation of v_t for n = 6α

Vertices d (v_t, P₁) d (v_t, P₂) d (v_t, P₃) d (v_t, P₄)

v_2s+1 (0 ≤ s ≤ α) 0 1 α - s + 1 s + 1

v_2α+2s+3 (0 ≤ s ≤ α - 1) 0 s + 2 1 α - s

v_4α+2s+3 (0 ≤ s ≤ α - 2) 0 α - s s + 2 1

v_2s (1 ≤ s ≤ α) 1 0 α - s + 1 s

v_2α+2s+2 (0 ≤ s ≤ α - 1) 1 s + 1 0 α - s

v_4α+2s (1 ≤ s ≤ α) 1 α - s + 1 s 0

Vertices	d (v_t, P₁)	d (v_t, P₂)	d (v_t, P₃)	d (v_t, P₄)
v_2s+1 (0 ≤ s ≤ α)	0	1	α - s + 1	s + 1
v_2α+2s+3 (0 ≤ s ≤ α - 1)	0	s + 2	1	α - s
v_4α+2s+3 (0 ≤ s ≤ α - 2)	0	α - s	s + 2	1
v_2s (1 ≤ s ≤ α)	1	0	α - s + 1	s
v_2α+2s+2 (0 ≤ s ≤ α - 1)	1	s + 1	0	α - s
v_4α+2s (1 ≤ s ≤ α)	1	α - s + 1	s	0

Table 3

Representation of v_t for n = 6α + 1

Vertices	d (v_t, P₁)	d (v_t, P₂)	d (v_t, P₃)	d (v_t, P₄)
v_2s+1 (0 ≤ s ≤ α)	0	1	α - s + 1	s + 1
v_2α+2s+3 (0 ≤ s ≤ α - 1)	0	s + 2	1	α - s
v_4α+2s+3 (0 ≤ s ≤ α - 2)	0	α - s	s + 2	1
v_2s (1 ≤ s ≤ α)	1	0	α - s + 1	s
v_2α+2s+2 (0 ≤ s ≤ α - 1)	1	s + 1	0	α - s
v_4α+2s (1 ≤ s ≤ α)	1	α - s + 2	s	0
v _6α+1	1	1	α + 1	0

Table 4

Representation of v_t for n = 6α + 2

Vertices	d (v_t, P₁)	d (v_t, P₂)	d (v_t, P₃)	d (v_t, P₄)
v_2s+1 (0 ≤ s ≤ α - 1)	0	s + 2	1	α - s
v_2α+2s+1 (0 ≤ s ≤ α - 1)	0	α - s	s + 2	1
v_4α+2s+1 (0 ≤ s ≤ α - 2)	0	1	α - s	s + 2
v _6α	0	1	1	α + 1
v_4α+2s (0 ≤ s ≤ α - 1)	1	0	α - s + 1	s + 1
v _6α-1	1	0	1	α + 1
v_2s (1 ≤ s ≤ α - 1)	1	s + 2	0	α - s
v _6α+1	1	1	0	α + 1
v _6α+2	1	2	0	α
v_2α+2s (0 ≤ s ≤ α - 1)	1	α - s	s + 1	0

Table 5

Representation of v_t for n = 6α + 3

Vertices	d (v_t, P₁)	d (v_t, P₂)	d (v_t, P₃)	d (v_t, P₄)
v ₁	0	2	α + 1	1
v_s (2 ≤ s ≤ 3)	0	1	α - s + 4	s - 1
v_α+2s (0 ≤ s ≤ α - 2)	0	1	α - s	s + 3
v _2α+4	0	2	1	α + 1
v _2α+3	0	1	1	α + 2
v_3α+2s+1 (0 ≤ s ≤ α - 2)	0	s + 3	1	α - s
v _5α+9	0	α + 1	2	1
v_5α+2s+2 (0 ≤ s ≤ α - 3)	0	α - s	s + 3	1
v ₄	1	0	α + 1	2
v_2s+1 (2 ≤ s ≤ α)	1	0	α - s + 2	s + 1
v _2α+5	1	2	0	α + 1
v_2α+2s+4 (1 ≤ s ≤ α - 1)	1	s + 2	0	α - s + 1
v _5α	1	α + 1	2	0
v_5α+2s+1 (0 ≤ s ≤ α - 2)	1	α - s	s + 3	0

Table 6

Partitions for n = 6α + 4 and α = 1, 2, 3, 4, 5

α	P ₁	P ₂	P ₃	P ₄
1	v₁, v₂, v₃	v₄, v₆	v₅, v₇, v₉	v₈, v₁₀
2	v₁, v₂, v₃, v₅, v₁₅	v₄, v₆, v₈	v₇, v₉, v₁₀, v₁₁, v₁₃	v₁₂, v₁₄, v₁₆
3	v₁, v₂, v₃, v₅, v₁₉, v₂₁	v₄, v₆, v₇, v₈, v₁₀	v₉, v₁₁, v₁₂, v₁₃, v₁₅, v₁₇	v₁₄, v₁₆, v₁₈, v₂₀, v₂₂
4	v₁, v₂, v₃, v₅, v₇, v₂₅, v₂₇	v₄, v₆, v₈, v₉, v₁₂, v₁₄	v₁₁, v₁₃, v₁₅, v₁₆, v₁₇, v₁₉, v₂₁	v₁₈, v₂₀, v₂₂, v₂₃, v₂₄, v₂₆, v₂₈
5	v₁, v₂, v₃, v₅, v₇, v₉, v₂₉, v₃₁, v₃₃	v₄, v₆, …, v₁₈	v₁₁, v₁₃, …, v₂₇	v₂₀, v₂₂, …, v₃₄

Table 7

Representation of v_t for n = 16 + 24p and p ≥ 1

Vertices	d (v_t, P₁)	d (v_t, P₂)	d (v_t, P₃)	d (v_t, P₄)
v ₁	0	2	α - 1	1
v ₂	0	1	α	1
v_2s+1 (1 ≤ s ≤ α - 1)	0	1	α - s	s + 1
v_5α+2s+1 (1 ≤ s ≤ α - 2)	0	α - s + 1	s	1
v_2s (2 ≤ s ≤ α)	1	0	α - s + 1	s
v_2α+2s (1 ≤ s ≤ α - 2)	s + 1	0	1	α - s
v_2α+2s+1 (0 ≤ s ≤ α - 2)	s + 1	1	0	α - s
v_3α+2s+1 (2 ≤ s ≤ α)	α - s + 1	s	0	1
v _12p+10	α	1	0	1
v_4α+2s(0 ≤ s ≤ α - 3)	α - s - 1	s + 2	1	0
v_5α+2s (1 ≤ s ≤ α - 1)	1	α - s + 1	s	0

Table 8

Representation of v_t for n = 22 + 24p and p ≥ 1

Vertices	d (v_t, P₁)	d (v_t, P₂)	d (v_t, P₃)	d (v_t, P₄)
v ₁	0	2	α - 1	1
v ₂	0	1	α	1
v_2s+1 (1 ≤ s ≤ α - 2)	0	1	α - s	s + 1
v_5α+2s (1 ≤ s ≤ α - 2)	0	α - s + 1	s	1
v _6p+7	1	0	1	α
v_2s (2 ≤ s ≤ α - 1)	1	0	α - s + 1	s
v_2α+2s (0 ≤ s ≤ α - 3)	s + 2	0	1	α - s - 1
v_2α+2s+1 (0 ≤ s ≤ α - 3)	s + 2	1	0	α - s - 1
v _12p+12	α	1	0	1
v_3α+2s(2 ≤ s ≤ α)	α - s + 1	s	0	1
v_3α+2s+3 (1 ≤ s ≤ α - 1)	α - s	s + 1	1	0
v_5α+2s+1 (1 ≤ s ≤ α - 2)	1	α - s	s + 1	0

Table 9

Representation of v_t for n = 28 + 24p and p ≥ 1

Vertices	d (v_t, P₁)	d (v_t, P₂)	d (v_t, P₃)	d (v_t, P₄)
v ₁	0	2	α - 1	1
v ₂	0	1	α	1
v_2s+1 (1 ≤ s ≤ α - 2)	0	1	α - s	s + 1
v_5α+2s+1 (1 ≤ s ≤ α - 3)	0	α - s	s + 1	1
v _6p+9	1	0	1	α
v_2s (2 ≤ s ≤ α - 1)	1	0	α - s + 1	s
v_2α+2s (0 ≤ s ≤ α - 3)	s + 2	0	1	α - s - 1
v_2α+2s+1 (0 ≤ s ≤ α - 3)	s + 2	1	0	α - s - 1
v _12p+16	α	1	0	1
v_3α+2s+3(1 ≤ s ≤ α - 2)	α - s	s + 1	0	1
v_3α+2s+4 (1 ≤ s ≤ α - 2)	α - s	s + 1	1	0
v _18p+23	1	α	1	0
v_5α+2s (1 ≤ s ≤ α - 2)	1	α - s	s + 1	0

Table 10

Representation of v_t for n = 34 + 24p and p ≥ 1

Vertices	d (v_t, P₁)	d (v_t, P₂)	d (v_t, P₃)	d (v_t, P₄)
v ₁	0	2	α - 2	1
v ₂	0	1	α - 1	1
v_2s+1 (1 ≤ s ≤ α - 2)	0	1	α - s - 1	s + 1
v_5α+2s (1 ≤ s ≤ α - 3)	0	α - s	s	1
v_2s (2 ≤ s ≤ α - 1)	1	0	α - s	s
v_2α+2s (0 ≤ s ≤ α - 3)	s + 2	0	1	α - s - 2
v_2α+2s-1 (0 ≤ s ≤ α - 2)	s + 1	1	0	α - s - 1
v_3α+2s+6(0 ≤ s ≤ α - 3)	α - s - 2	s + 2	0	1
v_3α+2s+5 (0 ≤ s ≤ α - 2)	α - s - 1	s + 1	1	0
v_5α+2s+1 (1 ≤ s ≤ α - 3)	1	α - s - 1	s + 1	0

Table 11

Representation of v_t for n = 6α + 5

Vertices	d (v_t, P₁)	d (v_t, P₂)	d (v_t, P₃)	d (v_t, P₄)
v ₁	0	2	α + 1	1
v_s (2 ≤ s ≤ 3)	0	1	α - s + 4	s - 1
v_α+2s (0 ≤ s ≤ α - 1)	0	1	α - s	s + 3
v _5α	0	α + 2	1	1
v _5α+1	0	α + 1	2	1
v_5α+2s+2 (1 ≤ s ≤ α - 2)	0	α - s + 1	s + 2	1
v_3α+2s+1 (0 ≤ s ≤ α - 1)	0	s + 2	1	α - s + 1
v ₄	1	0	α + 1	2
v_2s+1(2 ≤ s ≤ α + 1)	1	0	α - s + 2	s + 1
v _2α+5	1	1	0	α + 2
v_3α+2s (0 ≤ s ≤ α - 1)	1	s + 2	0	α - s + 1
v _5α+2	1	α + 1	2	0
v_5α+2s+1 (1 ≤ s ≤ α - 1)	1	α - s + 1	s + 2	0

Now the only case left is C₁₁ (1, 2). To prove its 2-partition dimension, we first give an important result on C₁₁ (1, 2).

Lemma 3.4. Let Γ = {P₁, P₂, P₃, P₄} be a partition of V (C₁₁ (1, 2)).

If |P_i|=1 for some 1 ≤ i ≤ 4, then d (v, P_i) =3 for exactly two v ∈ V (C₁₁ (1, 2)).

If |P_i|=2 for some 1 ≤ i ≤ 4, then d (v, P_i) =3 for at most one v ∈ V (C₁₁ (1, 2)).

If |P_i|≥3 for some 1 ≤ i ≤ 4, then d (v, P_i) ≤2 for all v ∈ V (C₁₁ (1, 2)).

Proof.

If P_i = {v_j} for some 1 ≤ i ≤ 4, then d (v_j+1, P_i) = d (v_j+2, P_i) = d (v_j-1, P_i) = d (v_j-2, P_i) =1 and d (v_j+3, P_i) = d (v_j+4, P_i) = d (v_j-3, P_i) = d (v_j-4, P_i) =2. Hence exactly two vertices are left which are at distance three from v_j, namely v_j+5 and v_j-5.

If |P_i| = {v_j-1, v_j} containing two consecutive vertices of V (C₁₁ (1, 2)), then there is only one vertex namely, v_j+5 at distance three from P_i. In all other cases distance would be less than three.

The result follows from part (ii) as |P_i|≥3 then no vertex would be at distance three from P_i.■

In the next theorem, we compute the 2-partition dimension of C₁₁ (1, 2).

Theorem 3.5. The pd₂ (C₁₁ (1, 2)) =5 .

Proof.

It is easy to check that Γ = {P₁, P₂, P₃, P₄, P₅} of V (C₁₁ (1, 2)) where P₁ = {v₁, v₂, v₃, v₄}, P₂ = {v₅, v₆, v₇} , P₃ = {v₈} , P₄ = {v₉, v₁₁} and P₅ = {v₁₀} is a 2-partition generator of C₁₁ (1, 2).

By Lemma 3 we know that pd₂ (C₁₁ (1, 2)) ≥4. We only need to show that pd₂ (C₁₁ (1, 2)) ≠4. Assume that pd₂ (C₁₁ (1, 2)) =4. Let Γ = {P₁, P₂, P₃, P₄} be a 2-partition basis of V (C₁₁ (1, 2)). If we take |P₁| ≥ |P₂| ≥ |P₃| ≥ |P₄|, then P₁ will have at least three vertices. i.e. |P₁|≥3.

Let v_t ∈ V (C₁₁ (1, 2)) then r (v_t|Γ) = (a_i, b_i, c_i, d_i) where a_i, b_i, c_i, and d_i are the distances of v_t from P₁, P₂, P₃ and P₄ respectively.

When |P₁|=8, |P₂| = |P₃| = |P₄|=1.

Here Lemma 3 implies that 0 ≤ a_i ≤ 2 and 1 ≤ b_i, c_i, d_i ≤ 3. Lemma 3 also implies that exactly two b_i, two c_i and two d_i have value 3. The seven out of eight representations of vertices in P₁ can be chosen as follows: (0, 1, 1, 1) , (0, 1, 2, 2) , (0, 1, 3, 3) , (0, 2, 2, 1), (0, 2, 1, 2), (0, 3, 3, 2) and (0, 3, 2, 3). But the representation of 8^th vertex cannot be chosen in a way that make all representations distinct in at least two places. This leads to a contradiction.

When |P₁|=7, |P₂|=2, |P₃| = |P₄|=1.

Here Lemma 3 implies that 0 ≤ a_i ≤ 2 and 1 ≤ b_i, c_i, d_i ≤ 3 with at most one b_i can be 3. Lemma 3 also implies that exactly two c_i and two d_i have value 3. The six out of seven representations of vertices in P₁ can be chosen as follows: (0, 1, 1, 1) , (0, 1, 2, 2) , (0, 1, 3, 3), (0, 2, 2, 1), (0, 2, 1, 2) and (0, 3, 3, 2). But the representation of 7^th vertex cannot be chosen in a way that make all representations distinct in at least two places. This leads to a contradiction.

When |P₁|=6.

|P₂|=3, |P₃| = |P₄|=1.

Here Lemma 3 implies that 0 ≤ a_i, b_i ≤ 2 and 1 ≤ c_i, d_i ≤ 3. Lemma 3 also implies that exactly two c_i and two d_i have value 3. The five out of six representations of vertices in P₁ can be chosen as follows: (0, 1, 1, 1) , (0, 1, 2, 2) , (0, 1, 3, 3), (0, 2, 2, 1) and (0, 2, 1, 2). But the representation of 6^th vertex cannot be chosen in a way that make all representations distinct in at least two places. This leads to a contradic-tion.

|P₂|=2, |P₃|=2, |P₄|=1.

This case is similar to Case 3.1.

When |P₁|=5.

|P₂|=3, |P₃|=2, |P₄|=1.

Here Lemma 3 implies that 0 ≤ a_i, b_i ≤ 2 and 1 ≤ c_i, d_i ≤ 3. Lemma 3 also implies that at most one c_i and exactly two d_i have value 3. The four out of five representations of vertices in P₁ can be chosen from one of the following sets of representations:

{(0, 1, 1, 1) , (0, 1, 2, 2) , (0, 2, 2, 1) , (0, 2, 1, 2)} or

{(0, 1, 1, 1) , (0, 1, 2, 2) , (0, 2, 1, 2) , (0, 2, 3, 1)} or

{(0, 1, 1, 1) , (0, 1, 3, 2) , (0, 1, 2, 3) , (0, 2, 1, 3)}.

Now the 5^th vertex cannot be chosen in a way that make all representations distinct in at least two places. This leads to a contradiction.

|P₂|=4, |P₃| = |P₄|=1.

This case is similar to Case 4.1.

|P₂|=2, |P₃|=2, |P₄|=2.

This case is also similar to Case 4.1.

When |P₁|=4.

|P₂|=4, |P₃|=2, |P₄|=1.

Here Lemma 3 implies that 0 ≤ a_i, b_i ≤ 2 and 1 ≤ c_i, d_i ≤ 3. Lemma 3 also implies that at most one c_i and exactly two d_i have value 3. The four representations of vertices in P₁ can be chosen from one of the following sets of representations:

{(0, 1, 1, 1) , (0, 1, 2, 2) , (0, 2, 2, 1) , (0, 2, 1, 2)} or

{(0, 1, 1, 1) , (0, 1, 2, 2) , (0, 2, 1, 2) , (0, 2, 3, 1)} or

{(0, 1, 1, 1) , (0, 1, 3, 2) , (0, 1, 2, 3) , (0, 2, 1, 3)}.

Now the representations of vertices in P₂ cannot be chosen in a way that make all representations distinct in at least two places. This leads to a contradiction.

|P₂|=3, |P₃|=3, |P₄|=1.

This case is similar to Case 5.1.

|P₂|=3, |P₃|=3, |P₄|=2.

This case is also similar to Case 5.1.

When |P₁|=3, |P₂|=3, |P₃|=3,

|P₄|=2.

Here Lemma 3 implies that 0 ≤ a_i, b_i, c_i, ≤ 2 and 1 ≤ d_i ≤ 3. Lemma 3 also implies that at most one d_i has value 3. The three representations of vertices in P₁ can be chosen from one of the following sets of representations:

{(0, 2, 1, 3) , (0, 1, 2, 1) , (0, 1, 1, 2)} or

{(0, 1, 1, 1) , (0, 1, 2, 2) , (0, 2, 2, 1)} or

{(0, 1, 1, 1) , (0, 1, 2, 2) , (0, 2, 1, 2)} or

{(0, 1, 1, 1) , (0, 2, 1, 3) , (0, 1, 2, 2)} or

{(0, 1, 2, 2) , (0, 2, 2, 1) , (0, 2, 1, 2)}.

If we consider the first set then P₄ coordinate of the representation can only be 3 if vertices in P₄ are consecutive. But then representations of vertices in P₂ cannot be chosen in a way that make all representations distinct in at least two places. This leads to a contradiction. Similar arguments can be given for other sets.

Thus in all the cases we proved that pd₂ (C₁₁ (1, 2)) ≠4. Hence pd₂ (C₁₁ (1, 2)) =5.■

Finally, we conclude the above discussion for the 2-partition dimension of C_n (1, 2) in the following theorem for n ≥ 6.

Theorem 3.6. Consider C_n (1, 2) for n ≥ 6 then ${pd}_{2} (C_{n} (1, 2)) = {\begin{matrix} 4, & when n \neq 11; \\ 5, & when n = 11 . \end{matrix}$

4 Conclusion

In this paper, we computed partition dimension of circulant graphs C_n (1, 2) for n ≡ 2 (mod 4), n ≥ 18 and hence corrected the result given by Salman et al. in [42]. Further, it is proved that 2-partition dimension of C_n (1, 2) for n ≥ 6, n ≠ 11 is 4 and for n = 11 it is 5. Hence the partition dimension and 2-partition dimension of C_n (1, 2) for n ≥ 6 does not dependent on the number of vertices of the graph. The paper is concluded by the following open problem.

Open Problem 4.1. Compute the 2-partition dimension of circulant graphs C_n (1, 2, 3) for n ≥ 10.

Footnotes

Acknowledgment

The authors are grateful to the reviewer’s valuable comments that improved the manuscript.

References

Amrullah

B.E.T.

, Simanjuntak

and Uttunggadewa

, The Partition Dimension of a Subdivision of a Complete Graph, Procedia Comput Sci 74 (2015), 53–59.

Amanathulla

Sk.

and Pal

, L(0; 1)- and L(1; 1)-labelling problems on circular- arc graphs, Int J Soft Comput 11(6) (2016), 343–350.

Amanathulla

Sk.

and Pal

, L (3; 2; 1)- and L (4; 3; 2; 1)-labelling problems on circular-arc graphs, Int J Control Theory Appl 9(34) (2016), 869–884.

Amanathulla

Sk.

and Pal

, L(3,2,1)- and L(4,3,2,1)- labeling problems on interval graphs, AKCE Int J Graphs Comb 14(3) (2017), 205–215.

Amanathulla

Sk.

and Pal

, L (3; 2; 1)-labelling problems on permutation graphs, Transylvanian Review 25(14) (2017), 3939–3953.

Amanathulla

Sk.

, Pal

and Surjective

, (2; 1)-labelling of cycles and circular-arc graphs, JIFS 35(1) (2018), 739–748.

Azhar

, Zafar

, Kashif

and Zahid

, On faulttolerent partition dimension of graphs, J Intell Fuzzy Syst 40 (2021), 1129–1135.

Boesch

and Tindell

, Circulants and their connectivities, J Graph Theor 8(4) (1984), 487–499.

Boesch

and Wang

J.F.

, Reliable circulant networks with minimum transmission delay, Circuits Syst, IEEE Trans 32(12) (1985), 1286–1291.

10.

Chartrand

, Eroh

, Johnson

M.A.

and Oellermann

O.R.

, Resolvability in graphs and the metric dimension of a graph, Discrete Appl Math 105 (2000), 99–113.

11.

Chaudhry

M.A.

, Salman

and Javaid

, Fault-tolerant metric and partition dimension of graphs, Utilitas Mathematica 83 (2010), 187–199.

12.

Chartrand

, Salehi

and Zhang

, The partition dimension of a graph, Aequ Math 59 (2000), 45–54.

13.

Dewi

M.P.K.

and Kusmayadi

T.A.

, On the partition dimension of a lollipop graph and a generalized Jahangir graph, J Phys Conf Ser 855(1) (2017).

14.

Doorn

E.A.V.

, Connectivity of circulant digraphs, J Graph Theor 10(1) (1986), 9–14.

15.

Estrado-Moreno

, On the-partition dimension of graphs, Theor Compu Sci 806 (2020), 42–52.

16.

Estrado-Moreno

, Rodriguez-Velaquez

J.A.

and Yero

I.G.

, The-metric dimension of a graph, Appl Math Inf Sci 9(6) (2015), 2829–2840.

17.

Fernau

, Rodriguez-Velaquez

J.A.

and Yero

I.G.

, On the partition dimension of unicyclic graphs, Bulletin Mathématique De La Société Des Sciences Mathématiques De Roumanie, Nouvelle Série 57(105) (2014), 381–391.

18.

Fredlina

K.Q.

and Baskoro

E.T.

, The partition dimension of some families of trees, Procedia Comput Sci 74 (2015), 60–66.

19.

Garey

M.R.

and Johnson

D.S.

, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, New York (1979).

20.

Grigorious

, Kalinowski

, Ryan

and Stephen

, The metric dimension of the circulant graph(±1,2, 3, 4), Australas. J. Combin 69(3) (2017), 417–441.

21.

Grigorious

, Stephen

, Rajan

and Miller

, On the partition dimension of circulant graphs, Comput J 60 (2017), 180–184.

22.

Grigorious

, Stephen

, Rajan

, Miller

and William

, On the partition dimension of a class of circulant graphs, Inf Process Lett 114 (2014), 353–356.

23.

Harary

and Melter

R.A.

, On the metric dimension of a graph, Theory Comput. Syst. Ars Combinatoria 2 (1976), 191–195.

24.

Haryeni

D.O.

, Baskoro

E.T.

and Saputro

S.W.

, On the partition dimension of disconnected graphs, J. Math Fund Sci 49(1) (2017), 18–32.

25.

Hernando

, Mora

, Slater

P.J.

and Wood

D.R.

, Fault-tolerant metric dimension of graphs, In Proceedings International Conference on Convexity in Discrete Structures; Ramanujan Mathematical Society: Tiruchirappalli, India (2008), 81–85.

26.

Hussain

, Khan

J.A.

, Munir

, Saleem

M.S.

and Iqbal

, Sharp bounds for partition dimension of generalized Mobius ladders, Open Math 16 (2018), 1283–1290.

27.

Imran

, Baig

A.Q.

and Rashid

, On the metric dimension and diameter of circulant graphs with three jumps, Discrete Math Algo and Apps 10(1) (2018), 17.

28.

Javaid

, Raja

N.K.

, Salman

and Azhar

M.N.

, The partition dimension of circulant graphs, World Appl Sci J 18 (2012), 1705–1717.

29.

Javaid

, Salman

, Chaudhry

M.A.

and Shokat

, Fault tolerance in resolvability, Utilitas Mathematica 80 (2009), 263–275.

30.

Khuller

, Raghavachari

and Rosenfeld

, Landmarks in Graphs, Discrete Appl. Math 70 (1996), 217–229.

31.

and Li

, Reliability analysis of circulant graphs[J], Networks 31(2) (1998), 61–65.

32.

Liu

J.B.

, Munir

, Ali

, Hussain

and Ahmed

, Fault-Tolerant metric dimension of wheel related graphs, < hal – 01857316v2 >, (2019).

33.

Maritz

E.C.M.

and Vetrik

, The partition dimension of circulant graphs, Quaest Math 41(1) (2018), 49–63.

34.

Mehreen

, Farooq

and Akhter

, On the partition dimension of fullerene graphs, AIMS Math 3(3) (2018), 343–352.

35.

Penso

L.D.

, Rautenbach

and Szwarcfiter

J.L.

, Connectivity and diameter in distance graphs, Networks 57(4) (2011), 310–315.

36.

Poulik

and Ghorai

, Detour g-interior nodes and detour g-boundary nodes in bipolar fuzzy graph with applications, Hacet J Math Stat 49(1) (2020), 106–119.

37.

Poulik

and Ghorai

, Certain indices of graphs under bipolar fuzzy environment with applications, Soft Comput 24(7) (2020), 5119–5131.

38.

Poulik

and Ghorai

, Note on “Bipolar fuzzy graphs with applications", Knowl-based Syst 192 (2020), 1–5.

39.

Poulik

and Ghorai

, Determination of journeys order based on graph’s Wiener absolute index with bipolar fuzzy information, Information Sciences 545 (2021), 608–619.

40.

Poulik

, Ghorai

and Xin

, Pragmatic results in Taiwan education system based IVFG & IVNG, Soft Comput (2020). https://doi.org/10.1007/s00500-020-05180-4.

41.

Raza

, Hayat

and Pan

X.F.

, On the fault-tolerant metric dimension of convex polytopes, Appl Math Comput 339 (2018), 172–185.

42.

Salman

, Javaid

and Chaudhry

M.A.

, Resolvability in circulant graphs, Acta Math. Sin. (Engl. Ser.) 28 (2012), 1851–1864.

43.

Santoso

and Darmaji , The partition dimension of cycle books graph, J Phys Conf Series 974(1) (2018), 1–8.

44.

Sebö

and Tannier

, On metric generators of graphs, Math Oper Res 29 (2004), 383–393.

45.

Siddiqui

H.M.A.

and Imran

, Computation of Metric Dimension and Partition Dimension of Nanotubes, J Comput Theor Nanos 2 (2015), 1–5.

46.

Slater

P.J.

, Leaves of Trees, In Proc. 6th Southeastern Conf. Combinatorics, Graph Theory, and Computing, Congressus Numerantium 14 (1975), 549–559.

47.

Yero

I.G.

, Estrado-Moreno

and Rodriguez-Velaquez

J.A.

, Computing the–metric dimension of graphs, Appl Math Comput 300 (2017), 60–69.

48.

Zhan

, Akram

and Sitara

, Novel decision-making method based on bipolar neutrosophic information, Soft Comput 23(20) (2019), 9955–9977.

49.

Zhan

, Masood

and Akram

, Novel decision-making algorithms based on intuitionistic fuzzy rough environment, Int J Mach Learn Cybern 10(6) (2019), 1459–1485.