Debi Oktia Haryeni, Edy Tri Baskoro, Suhadi Wido Saputro

Combinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Jalan Ganesa 10 Bandung, Indonesia

debioktia@gmail.com, {ebaskoro,suhadi}@math.itb.ac.id

In this paper, we propose a method for constructing new graphs from a given graph G so that the resulting graphs have the partition dimension at most one larger than the partition dimension of the graph G. In particular, we employ this method to construct a family of graphs with partition dimension 3.

Keywords: partition dimension, graph

Mathematics Subject Classification : 05C12, 05C15, 05C62

DOI: 10.5614/ejgta.2019.7.2.5

1. Introduction

Let G(V, E) be a (not necessarily connected) graph. Let x, y ∈ V (G), the distance d(x, y) between vertices x and y is the length of a shortest path connecting x to y in G. If there is no such a path, then define d(u, v) = ∞. In this case, the vertices x and y are in different components of G. Let A ⊆ V (G). The distance d(x, A) from vertex x to A in G is defined as

\[d(x, A) = \min\{d(x, y) : y \in A\}.\]

Let Λ = {A1, A2, . . . , Ak} be an ordered k-partition of V (G). Then, Aⁱ is called a partition class with respect to Λ. If there exists Aⁱ for some i such that d(x, Ai) = ∞ then we say that there

Received: 3 October 2018, Revised: 31 January 2019, Accepted: 30 March 2019.

is no representation of x with respect to \(\Lambda\). If \(d(x, A_i) < \infty\) for all \(A_i \in \Lambda\), then define the representation \(r(x|\Lambda)\) of x with respect to \(\Lambda\) as

\[r(x|\Lambda) = (d(x, A_1), d(x, A_2), \dots, d(x, A_k)).\]

The partition \(\Lambda\) is called a resolving partition of G if each vertex has a representation and all the representations are different. The partition dimension of G is the smallest integer k in which the graph G possesses a resolving partition of G with k partition classes, and it is denoted by pd(G) for a connected G or pdd(G) for a disconnected graph. In case of a disconnected graph G, we say that \(pdd(G) = \infty\) if there is no resolving k-partition of G for any integer \(k \ge 1\).

The study of the partition dimension of connected graphs was introduced by Chartrand et al. [5] with aims of finding a new way/method in attacking the problem of determining the metric dimension in graphs. In the metric dimension problem, we focus on finding the minimum cardinality of a resolving set for a connected graph G. A set \(W \subseteq V(G)\) is called a resolving set of G if for any two distinct vertices x and y, there exists \(w \in W\) such that \(d(x, w) \neq d(y, w)\). Further results for the metric dimension of graphs can be seen in [1, 2, 3, 4, 14, 15]. In 2015, the notion of the partition dimension of a graph was generalized by Haryeni et al. [12, 13] so that the notion can be applied to all graphs (connected as well as disconnected graphs).

Many results in finding the partition dimension for graphs have been obtained by various authors. Chartrand et al. [6] characterized all connected graphs of order \(n \geq 3\) with partition dimension either 2, n or n-1. Furthermore, all connected graphs of order \(n \geq 9\) with the partition dimension n-2 were characterized by Tomescu [17]. Up to now, the characterization of all connected graphs on n vertices with partition dimension k is still an open problem for any \(k \in [3, n-3]\). For particular classes of graphs, their partition dimensions have been obtained, for instances the class of unicylic graphs was obtained by Fernau et al. [8], Cayley digraphs by Fehr et al. [7] and circulant graphs by Grigorious et al. [9]. Moreover, Yero et al. studied the partition dimension of the Cartesian product and the strong product between two connected graphs [19, 18]. Rodríguez-Velázquez et al.[16] determined the partition dimension for the corona product of two graphs.

For a disconnected graph \(G = \bigcup_{i=1}^{m} G_i\), Haryeni et al. [12] derived the upper and lower bounds of the partition dimension of G (if it is finite), namely

\[\max\{pd(G_i): 1 \le i \le m\} \le pdd(G) \le \min\{|V(G_i)|: 1 \le i \le m\}.\]

In the same paper, some conditions for a disconnected graph H containing a linear forest with partition dimension 3 have been derived. The partition dimensions of some classes of disconnected graphs with homogeneous components, namely a disjoint union of stars, a disjoint union of double stars and a disjoint union of some cycles were also studied in [13]. Further results on the partition dimension of disconnected graphs with two components can be seen in [10]. Recently in [11], Haryeni et al. obtained certain families of graphs containing cycles with partition dimension 3.

In this paper, we continue investigating the partition dimension of general (disconnected and connected) graphs. We propose a method for constructing a new graph H from the previous graph G. The new graph H will have partition dimension at most one higher than the partition dimension of G. The previous graph G can be either disconnected or connected. Moreover, by this method, we could construct a big family of connected graphs with partition dimension G.

2. Main Results

Haryeni et al. (2017) showed the following three results which are useful to prove our main theorems.

Theorem 2.1. [12] Let \(G = \bigcup_{i=1}^{m} G_i\). If \(pdd(G) < \infty\), then \(\max\{pd(G_i) : 1 \le i \le m\} \le pdd(G) \le \min\{|V(G_i)| : 1 \le i \le m\}\).

Definition 2.1. [12] For \(m \geq 1\), let \(G = \bigcup_{i=1}^m G_i\) and \(\Lambda = \{A_1, A_2, \ldots, A_k\}\) be a resolving partition of G. For any integer \(t \geq 1\), a vertex v is called t-distance if \(d(v, A_j) = 0\) or t for any \(A_j \in \Lambda\). Such a partition \(\Lambda\) is called connected if every subgraph induced by \(A_j \cap V(G_i)\) is connected for every \(j \in [1, k]\) and \(i \in [1, m]\).

Lemma 2.1. [10] For \(k \in [3, n]\), any connected k-partition of \(P_n\) or \(C_n\) is a resolving partition.

Let G be a (not necessarily connected) graph and \(\Lambda = \{A_1, A_2, \dots, A_k\}\) be a minimum resolving partition of G. Two vertices \(x, y \in A_i\) for any \(i \in [1, k]\) are called independent with respect to \(\Lambda\) if there exist two distinct integers other than i, say j and l, such that \(d(x, A_j) - d(y, A_j) \neq d(x, A_l) - d(y, A_l)\). Otherwise, they are called dependent vertices. Furthermore, G is called independent if there exists a minimum resolving partition of G such that any two distinct vertices in the same class partition are independent. Otherwise, G is called a dependent graph.

For instance, it is clear that a cycle \(C_m\) with the vertex set \(V(C_m) = \{v_i : i \in [1, m]\}\) is an independent graph for all \(m \geq 3\), since we can define a minimum resolving 3-partition \(\Lambda = \{A_1, A_2, A_3\}\) of \(C_m\) where \(A_i = \{v_j : j \in [\lfloor \frac{(i-1)m}{3} + 1 \rfloor, \lfloor \frac{im}{3} \rfloor]\}\) for all \(i \in [1, 3]\) such that any two vertices of \(C_m\) are independent vertices with respect to \(\Lambda\). Other examples of independent graphs are the complete graph \(K_m\) and the disjoint union of stars \((m+1)K_{1,m}\) for all \(m \geq 3\). On the other hand, a path \(P_m\) and \(tK_{1,m}\) are dependent graphs for any \(m \geq 3\) and \(t \in [1, n]\).

Now, consider the graph G consisting of two components with pdd(G)=4 in Figure 1. If we consider the minimum resolving partition \(\Lambda_1=\{A_1,A_2,A_3,A_4\}\) of G where \(A_1=\{v_1,v_2,v_3,v_4,v_7,v_9,v_{14},v_{17}\},\ A_2=\{v_5,v_8,v_{10},v_{12},v_{13},v_{15},v_{18}\},\ A_3=\{v_6,v_{16}\}\) and \(A_4=\{v_{11},v_{19}\},\) then we can see that vertices \(v_1\) and \(v_4\) are dependent since \(r(v_1|\Lambda_1)=(0,1,1,3)\) and \(r(v_4|\Lambda_1)=(0,2,2,4)\). However, we can define another minimum resolving partition of G, namely \(\Lambda_2=\{B_1,B_2,B_3,B_4\}\) where \(B_1=\{v_1,v_2,v_9,v_{14},v_{17}\},\ B_2=\{v_3,v_4,v_7,v_{15},v_{18}\},\ B_3=\{v_5,v_8,v_{10},v_{12},v_{19}\}\) and \(B_4=\{v_6,v_{11},v_{13},v_{16}\}\) so that any two vertices of G with respect to \(\Lambda_2\) are independent. Therefore, G is independent.

Now we introduce the method to extend any graph so that the partition dimension of the resulting graph is the same as the one of the previous graph. Let G be a graph and \(A=(a_1,a_2,\ldots,a_k)\) be an ordered subset of vertices of G. A hair graph of G with respect to A, denoted by \(G[(a_1,a_2,\ldots,a_k);(n_1,n_2,\ldots,n_k)]\), is the graph obtained from G by attaching a path \(P_{n_i}\) with \(n_i \ (\geq 2)\) vertices to vertex \(a_i\) for all \(i \in [1,k]\). Furthermore, the set of all hair graphs obtained from the graph G are denoted by Hair(G).

In Figure 2 we give two different hair graphs of a cycle \(C_6\), namely (a) \(C_6[(a_1,a_2,a_3,a_5),(2,3,2,3)]\) and (b) \(C_6[(a_1,a_2,a_3,a_4,a_5,a_6),(2,2,2,2,2,2)]\), and two different hair graphs of a path \(P_5\), namely (c) \(P_5[(b_2,b_3,b_4);(2,2,2)]\) and (d) \(P_5[(b_2,b_3,b_4);(2,3,4)]\).

We present the upper bound of the partition dimension of the hair graphs, as follows.

Figure 1. An independent graph G with a minimum resolving partition \(\Lambda_2 = \{\{v_1, v_2, v_9, v_{14}, v_{17}\}, \{v_3, v_4, v_7, v_{15}, v_{18}\}, \{v_5, v_8, v_{10}, v_{12}, v_{19}\}, \{v_6, v_{11}, v_{13}, v_{16}\}\}.\)

Figure 2. Some hair graphs: (a) \(C_6[(a_1,a_2,a_3,a_5);(2,3,2,3)]\), (b) \(C_6[(a_1,a_2,a_3,a_4,a_5,a_6);(2,2,2,2,2)]\), (c) \(P_5[(b_2,b_3,b_4);(2,2,2)]\) and (d) \(P_5[(b_2,b_3,b_4);(2,3,4)]\).

Theorem 2.2. For an integer \(t \geq 1\), let \(G = \bigcup_{i=1}^t G_i\) where \(G_i\) is a connected graph of order \(m_i \geq 3\) for any i and \(pdd(G) < \infty\). For any \(H \in Hair(G)\) then

\[pdd(H) \le \begin{cases} pdd(G), & \text{if } G \text{ is independent,} \\ pdd(G) + 1, & \text{if } G \text{ is dependent.} \end{cases}\]

Proof. Let \(V(G) = \{v_{i,p} : i \in [1,t], p \in [1,m_i]\}\) and \(\Lambda = \{A_1,A_2,\ldots,A_k\}\) be a minimum resolving partition of G. Let \(H \in \operatorname{Hair}(G)\), namely the graph obtained by identifying an endpoint of a path \(P_{n_{i,p}}\) to the vertex \(v_{i,p} \in V(G)\). Let \(V_N = \{v_{i,p}^a : i \in [1,t], p \in [1,m_i], a \in [1,n_{i,p}-1]\}\) be the set of all the new vertices of H. Now, we distinguish two cases.

Case 1. G is an independent graph. Thus, we can assume that G is an independent graph with respect to \(\Lambda\). Define a new partition \(\Lambda_1 = \{A'_1, A'_2, \ldots, A'_k\}\) of H where \(A'_l = A_l \cup \{v^a_{i,p} : v_{i,p} \in A_l, a \geq 1\}\) for all \(l \in [1, k]\). To prove that \(\Lambda_1\) is a resolving partition of H, we will show that any two distinct vertices \(x, y \in V(H)\) in \(A'_q\) for some \(q \in [1, k]\) have distinct representations with respect to \(\Lambda_1\). We consider three subcases.

Subcase 1.1. \(x, y \notin V_N\). Then, \(r(x|\Lambda_1) = r(x|\Lambda) \neq r(y|\Lambda) = r(y|\Lambda_1)\).

Subcase 1.2. \(x \notin V_N\) and \(y \in V_N\). We consider two subcases.

Subcase 1.2.1. \(x = v_{i,j}\) and \(y = v_{i,j}^a\) for some \(a \ge 1\). Then, \(d(x, A_s') < d(x, A_s') + a = d(y, A_s')\) for all \(s \ne q\). Therefore, \(r(x|\Lambda_1) \ne r(y|\Lambda_1)\).

Subcase 1.2.2. \(x = v_{i,j}\) and \(y = v_{b,c}^a\) where \(i \neq b\) and \(a \geq 1\). Since G is independent, the two vertices \(v_{i,j}, v_{b,c} \in V(G)\) are independent with respect to \(\Lambda\). By Subcase 1.1, we obtain that \(v_{i,j}\)

and \(v_{b,c}\) are also independent in H with respect to \(\Lambda_1\). Therefore, there exist two distinct integers \(s_1, s_2 \in [1, k] \setminus \{q\}\) such that \(d(v_{i,j}, A'_{s_1}) - d(v_{b,c}, A'_{s_1}) \neq d(v_{i,j}, A'_{s_2}) - d(v_{b,c}, A'_{s_2})\). This is easy to see that \(d(y, A'_l) = d(v_{b,c}, A'_l) + a\) for all \(l \neq q\) and \(a \geq 1\). Now, we suppose for the contrary that \(r(x|\Lambda_1) = r(y|\Lambda_1)\). This implies that \(d(x, A'_s) = d(y, A'_s)\) for all \(s \in [1, k]\). However,

\[d(x, A'_{s_1}) - d(v_{b,c}, A'_{s_1}) - a = d(x, A'_{s_1}) - d(y, A'_{s_1})\] \[= d(x, A'_{s_2}) - d(y, A'_{s_2})\] \[= d(v_{i,j}, A'_{s_2}) - d(v_{b,c}, A'_{s_2}) - a,\]

or \(d(v_{i,j}, A'_{s_1}) - d(v_{b,c}, A'_{s_1}) = d(v_{i,j}, A'_{s_2}) - d(v_{b,c}, A'_{s_2})\), a contradiction. Therefore, \(r(x|\Lambda_1) \neq r(y|\Lambda_1)\).

Subcase 1.3. \(x, y \in V_N\). We consider two subcases.

Subcase 1.3.1. \(x=v_{i,j}^{a_1}\) and \(y=v_{i,j}^{a_2}\) where \(a_1,a_2\geq 1\) and \(a_1\neq a_2\). Then, \(d(v_{i,j}^{a_1},A_s')=d(v_{i,j},A_s')+a_1=d(v_{i,j},A_s)+a_1\neq d(v_{i,j},A_s)+a_2=d(v_{i,j},A_s')+a_2=d(v_{i,j}^{a_2},A_s')\) for all \(s\neq q\). Therefore, \(r(x|\Lambda_1)\neq r(y|\Lambda_1)\).

Subcase 1.3.2. \(x=v_{i,j}^{a_1}\) and \(y=v_{b,c}^{a_2}\) where \(i\neq b\) and \(a_1,a_2\geq 1\). Similarly to Subcase 1.2.2, \(v_{i,j},v_{b,c}\in V(G)\) are independent vertices with respect to \(\Lambda_1,\,d(x,A_l')=d(v_{i,j},A_l')+a_1\) and \(d(y,A_l')=d(v_{b,c},A_l')+a_2\) for all \(l\neq q\). Therefore, there exist two distinct integers \(s_1,s_2\in [1,k]\setminus\{q\}\) such that \(d(v_{i,j},A_{s_1}')-d(v_{b,c},A_{s_1}')\neq d(v_{i,j},A_{s_2}')-d(v_{b,c},A_{s_2}')\). For the contrary, assume that \(r(x|\Lambda_1)=r(y|\Lambda_1)\), and so that \(d(x,A_s')=d(y,A_s')\) for all \(s\in [1,k]\). Thus, we have

\[[d(v_{i,j}, A'_{s_1}) + a_1] - [d(v_{b,c}, A'_{s_1}) + a_2] = d(x, A'_{s_1}) - d(y, A'_{s_1})\] \[= d(x, A'_{s_2}) - d(y, A'_{s_2})\] \[= [d(v_{i,j}, A'_{s_2}) + a_1] - [d(v_{b,c}, A'_{s_2}) + a_2],\]

or \(d(v_{i,j}, A'_{s_1}) - d(v_{b,c}, A'_{s_1}) = d(v_{i,j}, A'_{s_2}) - d(v_{b,c}, A'_{s_2})\), a contradiction. Therefore, \(r(x|\Lambda_1) \neq r(y|\Lambda_1)\).

Case 2. G is a dependent graph. Define a new partition \(\Lambda_2 = \{B'_1, B'_2, \dots, B'_k, B'_{k+1}\}\) of H where \(B'_i = A_i\) for all \(i \in [1, k]\) and \(B'_{k+1} = V_N\). We will verify that \(\Lambda_2\) is a resolving partition of H. We consider any two distinct vertices \(x, y \in V(H)\) in \(B'_q\) for some \(q \in [1, k+1]\). We distinguish two subcases.

Subcase 2.1 \(x,y \notin V_N\). Since \(\Lambda\) is a resolving partition of G, there exists \(s \in [1,k] \setminus \{q\}\) such that \(d(x,A_s) \neq d(y,A_s)\). By the definition of the partition \(\Lambda_2\) of H, we have \(d(x,B'_p) = d(x,A_p)\) and \(d(y,B'_p) = d(y,A_p)\) for all \(p \neq k+1\). Therefore, \(d(x,B'_s) = d(x,A_s) \neq d(y,A_s) = d(y,B'_s)\) and so that \(r(x|\Lambda_2) \neq r(y|\Lambda_2)\).

Subcase 2.2. \(x, y \in V_N\) and thus q = k + 1. We consider two subcases.

Subcase 2.2.1. \(x = v_{i,j}^{a_1}\) and \(y = v_{i,j}^{a_2}\) where \(a_1, a_2 \ge 1\) and \(a_1 \ne a_2\). Note that for any vertex \(v_{i,j}^a \in B'_{k+1}\) in V(H) and \(v_{i,j} \in A_l\) in V(G) for \(a \ge 1\) and \(l \in [1,k]\), \(d(v_{i,j}^a, B'_s) = d(v_{i,j}, B'_s) + a = d(v_{i,j}, A_s) + a\) for all \(s \in [1,k] \setminus \{l\}\). Therefore, we have \(d(x, B'_s) = d(v_{i,j}, B'_s) + a_1 = d(v_{i,j}, A_s) + a_1 \ne d(v_{i,j}, A_s) + a_2 = d(v_{i,j}, B'_s) + a_2 = d(y, B'_s)\). Thus, \(r(x|\Lambda_2) \ne r(y|\Lambda_2)\).

Subcase 2.2.2. \(x = v_{i,j}^{a_1}\) and \(y = v_{b,c}^{a_2}\) where \(i \neq b\) and \(a_1, a_2 \geq 1\). Let \(v_{i,j} \in B'_s\) and \(v_{b,c} \in B'_p\) for some \(s, p \in [1, k]\). If \(s \neq p\), then clearly x and y are resolved by both \(B'_s\) and \(B'_p\). Otherwise,

assume that s=p. Note that \(d(x,B'_l)=d(v_{i,j},B'_l)+a_1\) and \(d(y,B'_l)=d(v_{b,c},B'_l)+a_2\) for all \(l \notin \{s,k+1\}\). It is easy to see that for \(a_1 \neq a_2\), we have \(d(x,B'_s) \neq d(y,B'_s)\). On the other hand, if \(a_1=a_2\), then \(d(x,B'_t) \neq d(y,B'_t)\) for which \(d(v_{i,j},A_t) \neq d(v_{b,c},A_t)\) with respect to \(\Lambda\). Therefore, \(r(x|\Lambda_2) \neq r(y|\Lambda_2)\).

The upper bound of Theorem 2.2 is tight. For the case of independent graphs, the bound is achieved by the graph \(H\cong G[(v_1,v_2,v_{12},v_{13},v_{14});(4,4,3,2,2)]\) depicted in Figure 3. This graph is a hair graph of G in Figure 1. The partition \(\Lambda'=\{B_1',B_2',B_3',B_4'\}\) where \(B_1'=\{v_1,v_2,v_9,v_{14},v_{17},v_{20},v_{21},v_{23},v_{24},v_{25},v_{29}\}, B_2'=\{v_3,v_4,v_7,v_{15},v_{18},v_{22}\}, B_3'=\{v_5,v_8,v_{10},v_{12},v_{19},v_{26},v_{27}\}\) and \(B_4'=\{v_6,v_{11},v_{13},v_{16},v_{28}\}\) is a minimum resolving partition of H.

Figure 3. The graph \(G[(v_1, v_2, v_4, v_{12}, v_{13}, v_{14}); (3, 4, 2, 3, 2, 2)]\) where G is depicted in Figure 1.

Note that for \(m \geq 3\), the graphs \(C_m\) and \(P_m\) are independent and dependent graphs, respectively. The upper bound of Theorem 2.2 is also true for the hair graphs of \(C_m\) and \(P_m\), as follows.

Corollary 2.1. If \(H \in Hair(C_m)\) for any \(m \geq 3\), then pd(H) = 3.

Corollary 2.2. If \(H \in Hair(P_m)\) and \(H \not\cong P_n\) for any \(n \geq m\), then pd(H) = 3.

Let G be any dependent graph other than a path with pdd(G)=k. If G has a vertex v which is adjacent to k leaves and the hair graph \(H\in \operatorname{Hair}(G)\) has k+1 leaves, then pdd(H)=k+1. Furthermore, the upper bound of the partition dimension of \(H\in \operatorname{Hair}(G)\) of Theorem 2.2 can be improved. Consider a dependent graph G depicted in Figure 4. Let \(\Lambda_1=\{A_1,A_2,A_3\}\) be a resolving partition of G where \(A_1=\{v_1,v_4,v_{10},v_{11},v_{12},v_{13},v_{14}\}\), \(A_2=\{v_2,v_5,v_{15},v_{16},v_{17},v_{18}\}\) and \(A_3=\{v_3,v_6,v_7,v_8,v_9,v_{19}\}\). By the definition of partition \(\Lambda_1\), we have \(r(v_1|\Lambda_1)=(0,2,2), r(v_2|\Lambda_1)=(1,0,2), r(v_3|\Lambda_1)=(1,2,0), r(v_{12}|\Lambda_1)=(0,3,3), r(v_{16}|\Lambda_1)=(2,0,3)\) and \(r(v_8|\Lambda_1)=(2,3,0)\). Now, let \(H=G[(v_1,v_2,v_3);(2,2,2)]\) and let \(v_1',v_2',v_3'\) be the new vertices of H which are adjacent to \(v_1,v_2\) and \(v_3\), respectively. If we use the same method as in the proof of Theorem 2.2 to show that \(pdd(H) \leq pdd(G)\), then we have a partition \(\Lambda_1'=\{A_1',A_2',A_3'\}\) of V(H) where \(A_i'=A_i\cup\{v_i'\}\) for each \(1\leq i\leq 3\). Therefore, we obtain that \(r(v_1'|\Lambda_1')=(0,3,3)=d(v_{12}|\Lambda_1'), r(v_2'|\Lambda_1')=(2,0,3)=r(v_{16}|\Lambda_1'), \text{ and } r(v_3'|\Lambda_1')=(2,3,0)=r(v_8|\Lambda_1')\). This implies that \(\Lambda_1'\) is not a resolving partition of G'.

However, we can define another minimum resolving partition of G, namely \(\Lambda_2 = \{B_1, B_2, B_3\}\) where \(B_1 = \{v_1, v_4, v_{11}, v_{12}, v_{13}, v_{14}\}\), \(B_2 = \{v_2, v_5, v_9, v_{15}, v_{16}, v_{17}\}\) and \(B_3 = \{v_3, v_6, v_7, v_{15}, v_{16}, v_{17}\}\)

\(v_8, v_{10}, v_{18}, v_{19}\)}. By using the partition \(\Lambda_2\) of G, we can define the new partition of H using a similar method as in the proof of Theorem 2.2 so that \(pdd(H) \leq pdd(G)\), namely \(\Lambda'_2 = \{B'_1, B'_2, B'_3\}\) of G' where \(B'_i = B_i \cup \{v'_i\}\) for each \(1 \leq i \leq 3\). From the partition \(\Lambda'_2\), we can easily verify that \(r(x|\Lambda'_2) \neq r(y|\Lambda'_2)\) for any two distinct vertices \(x, y \in V(H)\).

Figure 4. A dependent graph G.

By those facts, we have the following conjecture.

Conjecture 1. Let G be a dependent graph of order \(n \ge 2\) and \(pdd(G) < \infty\). Let \(A = (b_1, b_2, \dots, b_k)\) be an ordered leaves of G and \(H' = G[(b_1, b_2, \dots, b_k); (n_1, n_2, \dots, n_k)]\). Then, \(pdd(H') \le pdd(G)\).

In the following results, we give some independent graphs consisting of two components with certain partition dimensions.

Theorem 2.3. For \(n \geq 3\), the graph \(C_3 \cup C_{2n}\) is an independent graph with a resolving 3-partition.

Proof. For \(n \ge 3\), let \(G = C_3 \cup C_{2n}\) where \(V(G) = V(C_3) \cup V(C_{2n}) = \{v_i : i \in [1,3]\} \cup \{u_j : j \in [1,2n]\}\). Certainly, \(pdd(G) \ge 3\). We define a 3-partition \(\Lambda = \{A_1, A_2, A_3\}\) of G such that:

\[A_{1} = \left\{ v_{1}, u_{j} : j \in \left[ 1, 2 \left\lceil \frac{n}{6} \right\rceil \right] \right\},\] \[A_{2} = \left\{ v_{2}, u_{j} : j \in \left[ 2 \left\lceil \frac{n}{6} \right\rceil + 1, 2 \left\lceil \frac{n}{6} \right\rceil + 2 \left\lceil \frac{n-2}{6} \right\rceil \right] \right\},\] \[A_{3} = \left\{ v_{3}, u_{j} : j \in \left[ 2 \left\lceil \frac{n}{6} \right\rceil + 2 \left\lceil \frac{n-2}{6} \right\rceil + 1, 2n \right\rceil \right\}.\]

By using the definition of the partition \(\Lambda\), clearly that each \(v_i\) is 1-distance vertex in \(A_i\) for \(i \in [1,3]\). Note that the cardinality of the partition class \(A_i\) is even for each \(i \in [1,3]\) in \(C_{2n}\). Hence clearly that \(C_{2n}\) does not contain any t-distance vertex with respect to \(\Lambda\). Since \(\Lambda\) is a connected partition in \(C_{2n}\), then \(\Lambda\) is a resolving partition of \(C_{2n}\) by Lemma 2.1. Therefore, \(\Lambda\) is a resolving partition of G.

Now, we will show that any two vertices in G are independent with respect to \(\Lambda\). Since each vertex \(v_i \in V(C_3)\) is 1-distance vertex and every vertex \(u_j \in V(C_{2n})\) is not a t-distance vertex for any t, we only need to consider any two distinct vertices \(u_a, u_b \in A_i\) for some \(i \in [1, 3]\). By the definition of the partition \(\Lambda\), for \(p \in [1, 2\lceil \frac{n}{6} \rceil], q \in [2\lceil \frac{n}{6} \rceil + 1, 2\lceil \frac{n}{6} \rceil + 2\lceil \frac{n-2}{6} \rceil]\) and \(r \in [2\lceil \frac{n}{6} \rceil + 2\lceil \frac{n-2}{6} \rceil + 1, 2n]\), we have

A method to construct graphs with certain partition dimension D. O. Haryeni et al.

\[d(u_p,A_k) = \begin{cases} 0, & \text{if } k = 1, \\ \min\{2\lceil\frac{n}{6}\rceil + 1 - p, p + 2n - (2\lceil\frac{n}{6}\rceil + 2\lceil\frac{n-2}{6}\rceil)\}, & \text{if } k = 2, \\ \min\{p,2\lceil\frac{n}{6}\rceil + 2\lceil\frac{n-2}{6}\rceil + 1 - p\}, & \text{if } k = 3, \end{cases}\] \[d(u_q,A_k) = \begin{cases} 0, & \text{if } k = 2, \\ \min\{q - 2\lceil\frac{n}{6}\rceil, 2n - q + 1\}, & \text{if } k = 1, \\ 2\lceil\frac{n}{6}\rceil + 2\lceil\frac{n-2}{6}\rceil + 1 - q, & \text{if } k = 3, \end{cases}\] \[d(u_r,A_k) = \begin{cases} 0, & \text{if } k = 3, \\ 2n - r + 1, & \text{if } k = 1, \\ r - 2\lceil\frac{n}{6}\rceil - 2\lceil\frac{n-2}{6}\rceil, & \text{if } k = 2. \end{cases}\]

Note that for a vertex \(u_p \in A_1\) where \(p \in [1, 2\lceil \frac{n}{6} \rceil]\), we have the following facts.

• 1. \(p+2n-(2\lceil \frac{n}{6}\rceil+2\lceil \frac{n-2}{6}\rceil)<2\lceil \frac{n}{6}\rceil+1-p \text{ if and only if } (2n\equiv 2 \mod 3 \text{ or } 2n\equiv 1 \mod 3)\) and p=1, so that \(d(u_1,A_2)=1+2n-(2\lceil \frac{n}{6}\rceil+2\lceil \frac{n-2}{6}\rceil).\)2. \(2\lceil \frac{n}{6}\rceil+2\lceil \frac{n-2}{6}\rceil+1-p\)
• \(2\lceil \frac{n}{6} \rceil + 2\lceil \frac{n-2}{6} \rceil + 1 2\lceil \frac{n}{6} \rceil = 2\lceil \frac{n-2}{6} \rceil + 1.\)

On the other hand, for a vertex \(u_q \in A_2\) where \(q \in \left[2\left\lceil\frac{n}{6}\right\rceil + 1, 2\left\lceil\frac{n}{6}\right\rceil + 2\left\lceil\frac{n-2}{6}\right\rceil\right]\), then \(2n - q + 1 < q - 2\left\lceil\frac{n}{6}\right\rceil\) if and only if \(2n \equiv 1 \mod 3\) and \(q = 2\left\lceil\frac{n}{6}\right\rceil + 2\left\lceil\frac{n-2}{6}\right\rceil\). This implies that \(d(u_{2\left\lceil\frac{n}{6}\right\rceil + 2\left\lceil\frac{n-2}{6}\right\rceil}, A_1) = 2n - (2\left\lceil\frac{n}{6}\right\rceil + 2\left\lceil\frac{n-2}{6}\right\rceil) + 1 = 2n - 2\left\lceil\frac{n}{6}\right\rceil - 2\left\lceil\frac{n-2}{6}\right\rceil + 1\).

By the above facts, we consider three cases.

Case 1. \(u_a, u_b \in A_1\) where \(a, b \in [1, 2\lceil \frac{n}{6} \rceil]\). If \((2n \equiv 2 \mod 3 \text{ or } 2n \equiv 1 \mod 3), a = 1\) and \(b \in [2, 2\lceil \frac{n}{6} \rceil - 1], \text{ then } d(u_a, A_2) - d(u_b, A_2) = (1 + 2n - (2\lceil \frac{n}{6} \rceil + 2\lceil \frac{n-2}{6} \rceil)) - (2\lceil \frac{n}{6} \rceil + 1 - b) = 2n - 4\lceil \frac{n}{6} \rceil - 2\lceil \frac{n-2}{6} \rceil + b = 2(n - 2\lceil \frac{n}{6} \rceil - \lceil \frac{n-2}{6} \rceil) + b \neq 1 - b = a - b = d(u_a, A_3) - d(u_b, A_3).\) If \(2n \equiv 2 \mod 3, a = 2\lceil \frac{n}{6} \rceil\) and \(b \in [2, 2\lceil \frac{n}{6} \rceil - 2],\) then \(d(u_a, A_2) - d(u_b, A_2) = (2\lceil \frac{n}{6} \rceil + 1 - a) - (2\lceil \frac{n}{6} \rceil + 1 - b) = -a + b = -2\lceil \frac{n}{6} \rceil + b \neq (2\lceil \frac{n-2}{6} \rceil + 1) - b = d(u_a, A_3) - d(u_b, A_3).\) Otherwise, \(d(u_a, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b, A_3) - d(u_b\)\(d(u_a, A_2) - d(u_b, A_2) = (2\lceil \frac{n}{6} \rceil + 1 - a) - (2\lceil \frac{n}{6} \rceil + 1 - b) = -a + b \neq a - b = d(u_a, A_3) - d(u_b, A_3).\)Hence, any two vertices in \(A_1\) are independent with respect to \(\Lambda\).

Case 2. \(u_a, u_b \in A_2\) where \(a, b \in [2\lceil \frac{n}{6}\rceil + 1, 2\lceil \frac{n}{6}\rceil + 2\lceil \frac{n-2}{6}\rceil]\). If \(2n \equiv 1 \mod 3\), \(a = 2\lceil \frac{n}{6}\rceil + 2\lceil \frac{n-2}{6}\rceil\) and \(b \in [2\lceil \frac{n}{6}\rceil + 1, 2\lceil \frac{n}{6}\rceil + 2\lceil \frac{n-2}{6}\rceil - 1]\), then \(d(u_a, A_1) - d(u_b, A_1) = (2n - 2\lceil \frac{n}{6}\rceil - 2\lceil \frac{n-2}{6}\rceil + 1) - (b - 2\lceil \frac{n}{6}\rceil) = 2n - 2\lceil \frac{n-2}{6}\rceil + 1 - b = 2(n - \lceil \frac{n-2}{6}\rceil) + 1 - b \neq -2\lceil \frac{n}{6}\rceil - 2\lceil \frac{n-2}{6}\rceil + b = -a + b = (2\lceil \frac{n}{6}\rceil + 2\lceil \frac{n-2}{6}\rceil + 1 - a) - (2\lceil \frac{n}{6}\rceil + 2\lceil \frac{n-2}{6}\rceil + 1 - b) = d(u_a, A_3) - d(u_b, A_3)\). Otherwise, \(d(u_a, A_1) - d(u_b, A_1) = (a - 2\lceil \frac{n}{6}\rceil) - (b - 2\lceil \frac{n}{6}\rceil) = a - b \neq -a + b = (2\lceil \frac{n}{6}\rceil + 2\lceil \frac{n-2}{6}\rceil + 1 - a)\)\(a)-(2\lceil \frac{n}{6}\rceil+2\lceil \frac{n-2}{6}\rceil+1-b)=d(u_a,A_3)-d(u_b,A_3)\). Therefore, any two vertices in \(A_2\) are independent with respect to \(\Lambda\).

Case 3. \(u_a, u_b \in A_3\) where \(a, b \in [2\lceil \frac{n}{6} \rceil + 2\lceil \frac{n-2}{6} \rceil + 1, 2n]\). Then \(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\)\(d(u_a, A_2) - d(u_b, A_2)\). Thus, any two vertices in \(A_3\) are independent with respect to \(\Lambda\).

By Theorems 2.2 and 2.3, we have the following corollary.

Corollary 2.3. If \(H \in Hair(C_3 \cup C_{2n})\) for any \(n \geq 3\), then pdd(H) = 3.

Theorem 2.4. For \(n \geq m \geq 4\), the graph \(K_m \cup C_n\) is an independent graph with a resolving m-partition.

Proof. For \(n \ge m \ge 4\), let \(G = K_m \cup C_n\) and \(V(G) = V(K_m) \cup V(C_n) = \{v_i : i \in [1, m]\} \cup \{u_j : j \in [1, n]\}\). Then, \(pdd(G) \ge m\). Let us define a partition \(\Lambda = \{A_1, A_2, \dots, A_m\}\) of G such that

\[A_i = \{v_i\} \cup \left\{u_j : j \in \left\lceil \left\lfloor \frac{(i-1)n}{m} \right\rfloor + 1, \left\lfloor \frac{in}{m} \right\rfloor \right\rceil \right\}, \text{ for each } i \in [1, m].\]

We will show that \(\Lambda\) is a resolving partition of G. This is easy to see that each vertex \(v_i \in K_m\) is 1-distance vertex with respect to \(\Lambda\). Now, consider a subgraph \(C_n\) of G. Since \(\Lambda\) is a connected partition of \(C_n\), then the partition \(\Lambda\) is a resolving partition of \(C_n\) by Lemma 2.1. Note that for any vertex \(x \in V(C_n)\) in \(A_i\) for some \(i \in [1, m]\), \(d(x, A_j) = d(x, A_k)\) at most for two different integers \(j, k \in [1, m]\). Since \(m \geq 4\), \(C_n\) does not contain any t-distance vertex with respect to \(\Lambda\). By these two facts, we can conclude that \(\Lambda\) is a resolving partition of \(G = K_m \cup C_n\).

Furthermore, we will show that any two vertices \(x, y \in V(G)\) in \(A_k\) for some \(k \in [1, m]\) are independent vertices. For \(x = v_i\) and \(y = u_j\) where \(i \in [1, m]\) and \(j \in [1, n]\), clearly that x and y are independent vertices. Now, we suppose for two distinct vertices \(x = u_j\) and \(y = u_l\) in \(A_k\). We consider three cases.

Case 1. \(x=u_j\) and \(y=u_l\) in \(A_1\) where \(j,l\in [1,\lfloor\frac{n}{m}\rfloor]\). Note that for a vertex \(u_j\in A_1\) where \(j\in [1,\lfloor\frac{n}{m}\rfloor]\), then \(d(u_j,A_2)=\lfloor\frac{n}{m}\rfloor+1-j\) and \(d(u_j,A_m)=j\). Therefore, we have \(d(x,A_2)-d(y,A_2)=-j+l\neq j-l=d(x,A_m)-d(y,A_m)\), so that any two distinct vertices \(x,y\in A_1\) are independent vertices with respect to the partition \(\Lambda\).

Case 2. \(x=u_j\) and \(y=u_l\) in \(A_k\) where \(j,l\in \lfloor \frac{(i-1)n}{m}\rfloor+1,\lfloor \frac{in}{m}\rfloor \rfloor\) and \(i\in [2,m-1]\). Note that for a vertex \(u_j\in A_k\) where \(j\in \lfloor \lfloor \frac{(i-1)n}{m}\rfloor+1,\lfloor \frac{in}{m}\rfloor \rfloor\) and \(k\in [2,m-1]\), then \(d(u_j,A_{i+1})=\lfloor \frac{in}{m}\rfloor+1-j\) and \(d(u_j,A_{i-1})=j-\lfloor \frac{(i-1)n}{m}\rfloor\). Therefore, we have \(d(x,A_{i+1})-d(y,A_{i+1})=-j+l\neq j-l=d(x,A_{i-1})-d(y,A_{i-1})\), so that any two distinct vertices \(x,y\in A_k\) for \(k\in [1,m-1]\) are independent vertices with respect to the partition \(\Lambda\).

Case 3. \(x=u_j\) and \(y=u_l\) in \(A_m\) where \(j,l\in \lfloor\lfloor\frac{(m-1)n}{m}\rfloor+1,n\rfloor\). Note that for a vertex \(u_j\in A_m\) where \(j\in \lfloor\lfloor\frac{(m-1)n}{m}\rfloor+1,n]\), we have \(d(u_j,A_1)=n-j+1\) and \(d(u_j,A_{m-1})=j-\lfloor\frac{(m-1)n}{m}\rfloor\). Therefore, we have \(d(x,A_1)-d(y,A_1)=-j+l\neq j-l=d(x,A_{m-1})-d(y,A_{m-1})\), so that any two distinct vertices \(x,y\in A_m\) are independent with respect to the partition \(\Lambda\).

By Theorems 2.2 and 2.4, we obtain the following corollary.

Corollary 2.4. For all \(n \geq m \geq 4\) and \(H \in Hair(K_m \cup C_n)\), \(pdd(H) \leq m\).

The upper bound of Corollary 2.4 is satisfied for the hair graph \(H = (K_m \cup C_n)[(v_1, u_1, u_2, \dots, u_n); (n_1, n_2, \dots, n_n, n_{n+1})]\) where \(v_1 \in V(K_m)\) and \(u_i \in V(C_n)\) for \(i \in [1, n]\).

Now, for \(m \geq 3\), let \(G = C_m \cup C_{m+3}\) where

\[\begin{array}{lll} V(G) & = & V(C_m) \cup V(C_{m+3}) \\ & = & \{v_i: i \in [1,m]\} \cup \{u_j: j \in [1,m+3]\} \text{ and} \\ E(G) & = & E(C_m) \cup E(C_{m+3}) \\ & = & \{v_iv_{i+1}, v_1v_m: i \in [1,m-1]\} \cup \{u_ju_{j+1}, u_1u_{m+3}: j \in [1,m+2]\}. \end{array}\]

Let \(F \subset E(C_{m+3})\) where \(F = \{u_j u_{j+1} : j \in [1, m+2], j \neq \lfloor \frac{m}{3} \rfloor + 1 \text{ and } j \neq \lfloor \frac{2m}{3} \rfloor + 2\}\). Furthermore, we define three new sets of edges \(E_1, E_2\) and \(E_3\) of G where

\[E_{1} = \left\{ v_{j}u_{j}, v_{j}u_{j+1} : 1 \leq j \leq \left\lfloor \frac{m}{3} \right\rfloor \right\},\] \[E_{2} = \left\{ v_{j}u_{j+1}, v_{j}u_{j+2} : \left\lfloor \frac{m}{3} \right\rfloor + 1 \leq j \leq \left\lfloor \frac{2m}{3} \right\rfloor \right\},\] \[E_{3} = \left\{ v_{j}u_{j+2}, v_{j}u_{j+3} : \left\lfloor \frac{2m}{3} \right\rfloor + 1 \leq j \leq m \right\}.\]

By the above notations, let \(G' = G \cup E_1 \cup E_2 \cup E_3\), \(G \subseteq G'' \subseteq G'\), \(F' \subseteq F\) and I = G - F'. Note that G'' and I are connected graphs. Then, we have the following result.

Theorem 2.5. The graphs G, G'' and I are independent graphs with resolving 3-partition.

Proof. Note that \(V(G) = V(G'') = V(I) = V(C_m) \cup V(C_{m+3}) = \{v_i : i \in [1, m]\} \cup \{u_j : j \in [1, m+3]\}\). To show that each of G, G'' and G is independent, define a minimum resolving partition for each of these graphs satisfying that any two vertices in the same partition class are independent. Clearly that pdd(G), pd(G''), \(pd(I) \geq 3\). Now, let G is a partition of G or G'' or G where

\[A_{1} = \left\{ v_{i}, u_{j} : i \in \left[1, \left\lfloor \frac{m}{3} \right\rfloor\right], j \in \left[1, \left\lfloor \frac{m}{3} \right\rfloor + 1\right] \right\},\] \[A_{2} = \left\{ v_{i}, u_{j} : i \in \left[\left\lfloor \frac{m}{3} \right\rfloor + 1, \left\lfloor \frac{2m}{3} \right\rfloor\right], j \in \left[\left\lfloor \frac{m}{3} \right\rfloor + 2, \left\lfloor \frac{2m}{3} \right\rfloor + 2\right] \right\},\] \[A_{3} = \left\{ v_{i}, u_{j} : i \in \left[\left\lfloor \frac{2m}{3} \right\rfloor + 1, m\right], j \in \left[\left\lfloor \frac{2m}{3} \right\rfloor + 3, m + 3\right] \right\}.\]

From the definition of partition \(\Lambda\), we have the representations of vertices of G or G'' or I with respect to \(\Lambda\) as follows.

\[r(v_i|\Lambda) = \begin{cases} (0, \lfloor \frac{m}{3} \rfloor + 1 - i, i), & \text{if } i \in [1, \lfloor \frac{m}{3} \rfloor], \\ (i - \lfloor \frac{m}{3} \rfloor, 0, \lfloor \frac{2m}{3} \rfloor + 1 - i), & \text{if } i \in [\lfloor \frac{m}{3} \rfloor + 1, \lfloor \frac{2m}{3} \rfloor], \\ (m - i + 1, i - \lfloor \frac{2m}{3} \rfloor, 0), & \text{if } i \in [\lfloor \frac{2m}{3} \rfloor + 1, m], \end{cases}\] \[r(u_j|\Lambda) = \begin{cases} (0, \lfloor \frac{m}{3} \rfloor + 2 - j, j), & \text{if } j \in [1, \lfloor \frac{m}{3} \rfloor + 1], \\ (j - \lfloor \frac{m}{3} \rfloor - 1, 0, \lfloor \frac{2m}{3} \rfloor + 3 - j), & \text{if } j \in [\lfloor \frac{m}{3} \rfloor + 2, \lfloor \frac{2m}{3} \rfloor + 2], \\ (m - j + 4, j - \lfloor \frac{2m}{3} \rfloor - 2, 0), & \text{if } j \in [\lfloor \frac{2m}{3} \rfloor + 3, m + 3]. \end{cases}\]

Let x and y be any two vertices of G, G'' or I in the same partition class of \(\Lambda\). If \((x=v_a \text{ and } y=v_b)\) or \((x=u_a \text{ and } y=u_b)\) in \(A_p\) for some \(p\in [1,3]\), clearly \(d(x,A_q)\neq d(y,A_q)\) for each \(q\neq p\) and \(a\neq b\). Therefore, \(r(x|\Lambda)\neq r(y|\Lambda)\) for any two vertices \(x,y\in V(C_m)\) or \(x,y\in V(C_{m+3})\). Now, we consider that \(x\in V(C_m)\) and \(y\in V(C_{m+3})\). For \(x=v_i\) and \(y=u_j\) in \(A_1\) where \(i\in [1,\lfloor\frac{m}{3}\rfloor]\) and \(j\in [1,\lfloor\frac{m}{3}\rfloor+1]\), if i=j, then \(d(x,A_2)=\lfloor\frac{m}{3}\rfloor+1-i=\lfloor\frac{m}{3}\rfloor+1-j<\lfloor\frac{m}{3}\rfloor+2-j=d(y,A_2)\). Otherwise, \(d(x,A_3)=i\neq j=d(y,A_3)\). For \(x=v_i\) and \(y=u_j\) in \(A_2\) where \(i\in [\lfloor\frac{m}{3}\rfloor+1,\lfloor\frac{2m}{3}\rfloor]\) and \(j\in [\lfloor\frac{m}{3}\rfloor+2,\lfloor\frac{2m}{3}\rfloor+2]\), if \(i-\lfloor\frac{m}{3}\rfloor=j-\lfloor\frac{m}{3}\rfloor-1\), then \(d(x,A_3)=\lfloor\frac{2m}{3}\rfloor+1-i=\lfloor\frac{2m}{3}\rfloor+1\)

\(\lfloor \frac{2m}{3} \rfloor + 2 - j < \lfloor \frac{2m}{3} \rfloor + 3 - j = d(y, A_3)\). Otherwise, \(d(x, A_1) = i - \lfloor \frac{m}{3} \rfloor \neq j - \lfloor \frac{m}{3} \rfloor - 1 = d(y, A_1)\). For \(x = v_i\) and \(y = u_j\) in \(A_3\) where \(i \in \lfloor \lfloor \frac{2m}{3} \rfloor + 1, m \rfloor\) and \(j \in \lfloor \lfloor \frac{2m}{3} \rfloor + 3, m + 3 \rfloor\), if \(i - \lfloor \frac{2m}{3} \rfloor = j - \lfloor \frac{2m}{3} \rfloor - 2\), then \(d(x, A_1) = m - i + 1 = m - j + 3 < m - j + 4 = d(y, A_1)\). Otherwise, \(d(x, A_2) = i - \lfloor \frac{2m}{3} \rfloor \neq j - \lfloor \frac{2m}{3} \rfloor - 2 = d(y, A_2)\). This implies that \(\Lambda\) is a resolving partition of each graph G, G'' or I.

Moreover, we will show that every two vertices x and y of G, or G'' or I in \(A_p\) for some \(p \in [1,3]\) are independent. Note for \((x=v_a \text{ and } y=v_b \text{ where } 1 \leq a < b \leq m)\) or \((x=u_a \text{ and } y=u_b \text{ where } 1 \leq a < b \leq m+3)\), then \(d(x,A_q)-d(y,A_q)=a-b \neq -(a-b)=d(x,A_r)-d(y,A_r)\) for some \(q \neq r\) not equal to p. Therefore, two vertices \(x,y \in C_m\) or \(x,y \in V(C_{m+3})\) are independent. Now, we suppose for \(x \in V(C_m)\) and \(y \in V(C_{m+3})\) in \(A_p\) for some \(p \in [1,3]\). If \(x=v_a\) and \(y=u_b\) in \(A_1\) where \(a \in [1,\lfloor \frac{m}{3}\rfloor]\) and \(b \in [1,\lfloor \frac{m}{3}\rfloor+1]\), then \(d(x,A_2)-d(y,A_2)=(\lfloor \frac{m}{3}\rfloor+1-a)-(\lfloor \frac{m}{3}\rfloor+2-b)=-a+b-1\neq a-b=d(x,A_3)-d(y,A_3)\). If \(x=v_a\) and \(y=u_b\) in \(A_2\) where \(a \in [\lfloor \frac{m}{3}\rfloor+1,\lfloor \frac{2m}{3}\rfloor]\) and \(b \in [\lfloor \frac{m}{3}\rfloor+2,\lfloor \frac{2m}{3}\rfloor+2]\), then \(d(x,A_1)-d(y,A_1)=(a-\lfloor \frac{m}{3}\rfloor)-(b-\lfloor \frac{m}{3}\rfloor-1)=a-b+1\neq -a+b-2=(\lfloor \frac{2m}{3}\rfloor+1-a)-(\lfloor \frac{2m}{3}\rfloor+3-b)=d(x,A_3)-d(y,A_3)\). If \(x=v_a\) and \(y=u_b\) in \(A_3\) where \(a \in [\lfloor \frac{2m}{3}\rfloor+1,m]\) and \(b \in [\lfloor \frac{2m}{3}\rfloor+3,m+3]\), then \(d(x,A_1)-d(y,A_1)=(m-a+1)-(m-b+4)=-a+b-3\neq a-b+2=(a-\lfloor \frac{2m}{3}\rfloor)-(b-\lfloor \frac{2m}{3}\rfloor-2)=d(x,A_2)-d(y,A_2)\). This concludes the proof.

In Figure 5 we give some independent graphs satisfying Theorem 2.5. These graphs are obtained from the graph \(C_5 \cup C_8\).

Figure 5. Independent graphs with resolving 3-partitions.

By Theorems 2.2 and 2.5, we have the following result.

Corollary 2.5. If \(H_1 \in Hair(G)\), \(H_2 \in Hair(G'')\) and \(H_3 \in Hair(I)\), then \(pdd(H_1) = pd(H_2) = pd(H_3) = 3\).

Acknowledgement

We express many thanks to the referees for the kind review and helpful suggestions. This research has been supported by the Research Grant: "Penelitian Dasar Unggulan Perguruan Tinggi (PDUPT)", the Ministry of Research, Technology and Higher Education, Indonesia.

References

[1] S. Akhter and R. Farooq, Metric dimension of fullerence graphs, Electron. J. Graph Theory Appl. 7 (1) (2019), 91-103.

• [2] M. Bac˘a, E.T. Baskoro, A.N.M. Salman, S.W. Saputro and D. Suprijanto, The metric dimension of regular bipartite graphs, Bull. Math. Soc. Sci. Math. Roumanie 54 (2011), 15–28.
• [3] J. Caceres, C. Hernando, M. Mora, I.M. Pelayo, M.L. Puertas and C. Seara, On the metric dimension of some families of graphs, Electron. Notes Discrete Math. 22 (2005), 129–133.
• [4] G. Chartrand, L. Eroh, M.A. Johnson and O.R. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math. 105 (2000), 99–113.
• [5] G. Chartrand, E. Salehi and P. Zhang, On the partition dimension of a graph, Congr. Numer. 131 (1998), 55–66.
• [6] G. Chartrand, E. Salehi and P. Zhang, The partition dimension of a graph, Aequationes Math. 59 (2000), 45–54.
• [7] M. Fehr, S. Gosselin and O. Oellermann, The partition dimension of Cayley digraphs, Aequationes Math. 71 (2006), 1–18.
• [8] H. Fernau, J.A. Rodr´ıguez-Velazquez and I.G. Yero, On the partition dimension of unicyclic ´ graphs, Bull. Math. Soc. Sci. Math. Roumanie 105 (2014), 381–391.
• [9] C. Grigorious, S. Stephen, B. Rajan and M. Miller, On partition dimension of a class of circulant graphs, Inform. Process. Lett. 114 (2014), 353–356.
• [10] D.O. Haryeni, E.T. Baskoro, S.W. Saputro, M. Baca and A. Semani ˇ cov ˇ a-Fe ´ nov ˇ cˇ´ıkova, On ´ the partition dimension of two-component graphs, Proc. Indian Acad. Sci. (Math. Sci.) 127 (5) (2017), 755–767.
• [11] D.O. Haryeni, E.T. Baskoro and S.W. Saputro, Family of graphs with partition dimension three, Submitted.
• [12] D.O. Haryeni, E.T. Baskoro and S.W. Saputro, On the partition dimension of disconnected graphs, J. Math. Fund. Sci. 49 (2017), 18–32.
• [13] D.O. Haryeni and E.T. Baskoro, Partition dimension of some classes of homogeneous disconnected graphs, Procedia Comput. Sci. 74 (2015), 73–78.
• [14] H. Iswadi, E.T. Baskoro, R. Simanjuntak, A.N.M. Salman, the metric dimension of graph with pendant edges, J. Combin. Math. Combin. Comput. 65 (2008), 139–145.
• [15] C. Poisson and P. Zhang, The metric dimension of unicyclic graphs, J. Combin. Math. Combin. Comput. 40 (2002), 17–32.
• [16] J.A. Rodr´ıguez-Velazquez, I.G. Yero and D. Kuziak, The partition dimension of corona prod- ´ uct graphs, Ars Combin. 127 (2016), 387–399.
• [17] I. Tomescu, Discrepancies between metric dimension and partition dimension of a connected graph, Discrete Math. 308 (2008), 5026–5031.

• [18] I.G. Yero, M. Jakovac, D. Kuziak and A. Taranenko, The partition dimension of strong product graphs and Cartesian product graphs, Discrete Math. 331 (2014), 43–52.
• [19] I.G. Yero, D. Kuziak and J.A. Rodr´ıguez-Velazquez, A note on the partition dimension of ´ Cartesian product graphs, Appl. Math. Comput. 217 (2010), 3571–3574.