1 Introduction

Chartrand, et al. [1] in 1998 introduced the idea for the partition dimension of connected graphs. This concept is a variant of the metric dimension of a graph described independently by Slater [2] in 1975 and by Harary & Melter [3] in 1976. Given a connected graph ܪ ൌ ሺܸ, ܧሻ, ݑ ∋ ܸሺܪሻ and ܲ ⊆ ܸሺܪሻ. The distance ݀ሺݑ, ܲሻ between ݑ and ܲ is minሼ݀ሺݑ, ݔሻ: ݔ ∋ ܲሽ, where ݀ሺݑ, ݔሻ denotes the distance between vertices ݑ and ݔ in ܪ. For an ordered ݐ-partition Ω ൌ ሼܲଵ, ܲଶ,…,ܲ௧ሽ of ܸሺܪሻ, the representation ݎሺݑ|Ωሻ of a vertex ݑ ∋ ܸሺܪሻ with respect to Ω is the ݐ-vector ሺ݀ሺݑ, ܲଵሻ, ݀ሺݑ, ܲଶሻ, ⋯ , ݀ሺݑ, ܲ௧ሻሻ. The partition Ω with ݐ classes is called a resolving partition if ݎሺݒ|Ωሻ ് ݎሺݓ|Ωሻ for any two distinct vertices ݒ, ݓ ∋ ܸሺܪሻ. The partition dimension of ܪ, denoted by ݀ሺܪሻ, is the minimum number of classes of a resolving partition Ω of ܪ.

In [4], Chartrand, et al. established a relation between the partition dimension and the metric dimension of a graph. They also proved that the only graph of order ݊2 with the partition dimension two is a path ܲ, while the only graph with the partition dimension ݊ is a complete graph ܭ. Furthermore, they characterized all graphs of order ݊3 with the partition dimension ݊െ1, namely ܭଵ,ିଵ , ܭ െ ݁ and ܭଵ ሺܭଵ ∪ ܭିଶሻ. Tomescu in [5] characterized all graphs ܩ of order ݊9 with ݀ሺܩሻ equal to ݊െ2. He also gave some

examples of graphs with a small partition dimension but having infinite metric dimension. These graphs are planar 4-regular (\(\mathbb{Z}^2\), \(\xi^4\)) and planar 8-regular (\(\mathbb{Z}^2\), \(\xi^8\)). The first graph has partition dimension 3 and the second one has partition dimension 4, but their metric dimensions are infinite.

The partition dimensions for various classes of connected graphs have been obtained. For instance, Tomescu, et al. [6] gave the upper bounds of the order of some wheel-related graphs, namely the gear, helm, sunflower and friendship graph, with a given partition dimension. Fehr, et al. [7] showed that the partition dimension of a Cayley digraph of a dihedral group of order \(2n, n \geq 3\) with a minimum generator is three. The partition dimensions of complete multipartite graphs, windmills and caterpillars have been obtained by Darmaji, et al. [8]. In 2014, Rodríguez-Velázquez, et al. [9] derived some upper bounds of the partition dimension of trees and Grigorious, et al. [10] gave the partition dimension of a class of circulant graphs. Recently, in 2015, Javaid, et al. [11] investigated the minimum connected resolving partitions in unicyclic graphs.

Some authors also studied the partition dimension of a graph obtained from some graph operations. Darmaji, et al. [12,13] and Rodríguez-Velázquez, et al. [14] gave the partition dimension for some corona graphs. The partition dimension of Cartesian product graphs and strong product graphs have been determined by Yero, et al. [15,16].

However, all results mentioned above are only for connected graphs. In this study, the notion of the partition dimension is generalized so that it can also be applied to disconnected graphs. Some lower and upper bounds for the partition dimension of disconnected graphs are determined (if they are finite). In this paper, also the partition dimensions for some classes of disconnected graphs are given.

2 Main Results

Given a general (connected or disconnected) graph G = (V, E). For each vertex \(w \in V(G)\) and a set \(O \subseteq V(G)\), define the distance d(w, O) between w and O to be \(\min\{d(w,x)\colon x\in O\}\). For an ordered partition \(\Omega=\{0_1,0_2,...,0_t\}\) of the vertices of G, if \(d(x,O_i)<\infty\) for every \(x\in V(G)\) and \(i\in [1,t]\), then we can define the representation \(r(x|\Omega)\) of x with respect to the partition \(\Omega\) as the t-vector \((d(x,O_1),d(x,O_2),\cdots,d(x,O_t))\). The partition \(\Omega\) is called a resolving partition if \(r(x|\Omega)\neq r(y|\Omega)\) for any two distinct vertices \(x,y\in V(G)\). The partition dimension of G, denoted by pd(G) if G is connected or pdd(G) if G is disconnected, is the least integer f (if any) such that G admits a resolving partition with f classes. Otherwise, we define f f f f f f f f f f

As an illustration of this concept, we consider a disconnected graph \(G = C_4 \cup P_5\) as depicted in Figure 1. Since \(pd(C_4) = 3\) and \(pd(P_5) = 2\), then by using the definition of the partition dimension of a disconnected graph, G has a finite partition dimension if both \(C_4\) and \(P_5\) have a resolving 3-partition. In fact pdd(G) = 3, since we can define a resolving partition \(\Omega = \{O_1, O_2, O_3\}\) with \(O_1 = \{u_1, v_1\}, O_2 = \{u_2, u_3, v_2\}\) and \(O_3 = \{u_4, v_3, v_4, v_5\}\). However, \(pdd(K_4 \cup K_{1,4}) = \infty\) since there exists no integer t so that \(K_4 \cup K_{1,4}\) has a resolving t-partition.

Figure 1 Graph \(G = C_4 \cup P_5\).

Now, for \(m \ge 2\) and the connected graphs \(G_i\), we consider a disconnected graph \(G = \bigcup_{i=1}^m G_i\) having a finite partition dimension. Let \(\Omega\) be a minimum resolving k-partition of G. Then by the definition of partition dimension of a disconnected graph, \(\Omega\) is also a resolving k-partition of \(G_i\) for every \(i \in [1, m]\). It follows that \(k \ge pd(G_i)\) for every i. Thus, \(k \ge \max\{pd(G_i): i \in [1, m]\}\). Furthermore, since \(\Omega\) is a resolving k-partition of \(G_i\), then \(k \le |V(G_i)|\) for every i. Therefore, \(k \le \min\{|V(G_i)|: i \in [1, m]\}\). So, we have the following theorem.

Theorem 1. For integer \(m \ge 2\), let \(G = \bigcup_{i=1}^m G_i\) and let \(G_i\) be a connected graph for every \(i \in [1, m]\). 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\}\). \(\square\)

For a connected graph \(G_i\), if \(G = \bigcup_{i=1}^m G_i\) containing a component consisting of a complete graph of order 1 or 2, then the following result shows that the partition dimension of G is finite if and only if m = 1.

Proposition 1. Let \(G = \bigcup_{i=1}^m G_i\) where \(m \ge 1\), \(G_i\) connected for each \(i \in [1, m]\), and there exists \(j \in [1, m]\) such that \(G_j \cong K_n\) for some \(n \in \{1, 2\}\). Then pdd(G) = n if m = 1. Otherwise, \(pdd(G) = \infty\).

Proof. For m = 1, we have \(G = K_n\) for some \(n \in \{1,2\}\). Therefore pdd(G) = n. For \(m \ge 2\) and n = 1, it is easy to see that \(pdd(G) = \infty\). Now we assume that \(m \ge 2\) and n = 2. Then, G contains \(K_2\) as its component. Suppose for the contrary that pdd(G) = 2 and \(\Omega = \{0_1, 0_2\}\) be any partition of G. Then, each

component of G must contain exactly two partition classes. Therefore, each component must be a path. But, there are \(u \in V(G_1)\) and \(v \in V(G_2)\) in \(O_1\) such that \(r(u|\Omega) = (0,1) = r(v|\Omega)\), a contradiction. \(\square\)

Corollary 1. Let \(P_n\) be a path with n vertices. For every \(m \ge 2, 3 \le pdd(mP_n) \le n\) if and only if \(n \ge 3\).

Proof. For \(m \ge 2\), let \(G = mP_n\) and \(n \ge 3\). By Theorem 1, we have \(pdd(G) \le n\). Now we will show that \(pdd(G) \ge 3\). We assume for the contrary that pdd(G) = 2. Then there are two vertices \(u, v \in V(G)\) such that \(r(u|\Omega) = (0,1) = r(v|\Omega)\) for any partition \(\Omega\) in G, a contradiction. \(\square\)

2.1 t-Distance Vertex and Connected Partition

For a partition \(\Omega = \{O_1, O_2, ..., O_k\}\) of a graph G and \(t \in \mathbb{N}\), we define a vertex \(x \in V(G)\) as a t-distance vertex if \(d(x, O_j) = 0\) or t for any \(O_j \in \Omega\). The next theorem gives the condition for a graph \(G = \bigcup_{i=1}^m G_i\) containing a component consisting of a complete graph \(K_n\) where \(n \geq 3\) such that pdd(G) is finite.

Theorem 2. For \(m \ge 1\), let \(G = \bigcup_{i=1}^m G_i\) and \(G_i\) be a connected graph for every \(i \in [1, m]\). If \(pdd(G) < \infty\) and there exists \(j \in [1, m]\) such that \(G_j \cong K_n\) where \(n \ge 3\), then pdd(G) = n and every component of \(G \setminus G_j\) has at least n vertices having no 1-distance vertex.

Proof. Let \(G = \bigcup_{i=1}^m G_i\) and suppose that there exists j such that \(G_j \cong K_n\) for some \(n \geq 3\). Since \(pdd(G) < \infty\) and for any graph H of order n, pd(H) = n if and only if \(H \cong K_n\), then pdd(G) = n. Let \(\Omega\) be any resolving n-partition of G. Then \(\Omega\) is also a resolving n-partition of \(G_i\) for any i. It follows that \(|V(G_i)| \geq n\) for every i. Since every \(v \in V(G_j)\) is adjacent with the remaining vertices of \(G_j\), those vertices are 1-distance. Therefore, other components must not contain a 1-distance vertex under \(\Omega\). \(\square\)

For a disconnected graph \(G = \bigcup_{i=1}^r G_i\) where \(G_i\) are connected for all \(i \in [1,r]\), the partition \(\Omega = \{O_1, O_2, ..., O_k\}\) of G is called a connected partition if every subgraph induced by \(O_j \cap V(G_i)\) for every \(1 \le j \le k\) and \(1 \le i \le r\) is connected. From now on, consider \(G = \bigcup_{i=1}^r P_{n_i}\) and \(v_{i,j}\) denotes the \(j^{th}\) vertex in the \(i^{th}\) component of G. For any resolving 3-partition of the \(i^{th}\) component of G, we define a left partition class \(L_i\) or a right partition class \(R_i\) as the partition class containing \(v_{i,1}\) or \(v_{i,n_i}\), respectively, while the remaining partition classes with no end-vertices are defined as a middle partition class \(M_i\).

In the following results, we give some properties of t-distance vertex in \(P_n\).

Lemma 1. Let \(P_n\) be a path of order \(n \ge 3\). If there exists a t-distance vertex in \(P_n\) for some \(t \ge 1\), then a resolving partition of \(P_n\) has cardinality 2 or 3.

Proof. For \(n \geq 3\), let \(\Omega = \{O_1, O_2, ..., O_k\}\) be a resolving partition of \(P_n\) and \(v \in O_r\) be a t-distance vertex for some \(r, t \geq 1\). Then for any vertex w in \(P_n\) with \(d(v, w) \leq t - 1\), we have \(w \in O_r\). Since \(\deg(v) \leq 2\), then there are at most two vertices at distance t from v. These vertices must be in \(O_i\) where \(i \neq t\). Therefore, k = 2 or 3. \(\square\)

Lemma 2. For some \(t \ge 1\) and \(n \ge 3\), if there exists a t-distance vertex under a resolving k-partition of \(P_n\), then \(t \le n-1\) for k=2, or \(t \le \left|\frac{n-1}{2}\right|\) for k=3.

Proof. Let \(\Omega = \{O_1, O_2, \dots, O_k\}\) be a resolving partition of \(P_n\) where \(n \geq 3\), and v be a t-distance vertex in \(P_n\). By Lemma 1 we have k = 2 or k = 3. If k = 2, then \(\max\{d(v, O_i): v \notin O_i\} = \operatorname{diam}(P_n) = n - 1\). Thus, \(t \leq n - 1\). If k = 3, then v must be at the middle position in \(P_n\) to have a maximum distance to two other partition classes \(O_i\) not containing v. Thus, \(t \leq \left|\frac{n-1}{2}\right|\). \(\square\)

Lemma 3. For \(n \ge 3\) and \(1 \le t \le \left\lfloor \frac{n-1}{2} \right\rfloor\), there exists a resolving 3-partition of \(3P_n\) such that every component has a t-distance vertex.

Proof. Let \(G = 3P_n\) where \(n \ge 3\), \(V(G) = \{v_{i,j} : 1 \le i \le 3, 1 \le j \le n\}\) and \(E(G) = \{v_{i,j}v_{i,j+1} : 1 \le i \le 3, 1 \le j \le n-1\}\). By Corollary 1, then \(pdd(G) \ge 3\). For any \(t \in \left[1, \left\lfloor \frac{n-1}{2} \right\rfloor\right]\) and \(i \in [1,3]\), let \(v_{i,\tau}\) be a t-distance vertex of the \(i^{th}\) component of G where \(t+1 \le \tau \le n-t\). Let \(\Omega = \{O_1, O_2, O_3\}\) be a partition of G induced by the function \(f_t : V(G) \to \{1, 2, 3\}\), as follows.

\[f_t(v_{i,j}) = \begin{cases} i \mod 3, & j = 1, 2, \dots, \tau - t, \\ i + 1 \mod 3, & j = \tau - t + 1, \tau - t + 2, \dots, \tau + t - 1, \\ i + 2 \mod 3, & \text{otherwise.} \end{cases}\]

Note that \(f_t(x) = i\) means that \(x \in O_i\). Thus, for any \(p \in [1, \tau - t]\), \(q \in [\tau - t + 1, \tau + t - 1]\) and \(r \in [\tau + t, n]\), we have

\[d(v_{i,p}, O_k) = \begin{cases} 0, & k = i \mod 3, \\ \tau - t + 1 - p, & k = i + 1 \mod 3, \\ \tau + t - p, & \text{otherwise,} \end{cases}\]

\[d(v_{i,q}, O_k) = \begin{cases} 0, & k = i + 1 \mod 3, \\ q - \tau + t, & k = i \mod 3, \\ \tau + t - q, & \text{otherwise,} \end{cases}\] \[d(v_{i,r}, O_k) = \begin{cases} 0, & k = i + 2 \mod 3, \\ r - \tau + t, & k = i \mod 3, \\ r - \tau - t + 1, & \text{otherwise.} \end{cases}\]

Let us consider any two vertices \(x,y \in O_k\). If \(x = v_{i,a}\) and \(y = v_{i,b}\) for some i,a,b where \(i \in [1,3]\), \(1 \le a < b \le \tau - t\), then \(d(x,O_{i+1 \bmod 3}) = \tau - t + 1 - a > \tau - t + 1 - b = d(y,O_{i+1 \bmod 3})\). If \(x = v_{i,a}\) and \(y = v_{i,b}\) where \(\tau - t + 1 \le a < b \le \tau + t - 1\) or \(\tau + t \le a < b \le n\) then \(d(x,O_{i \bmod 3}) = a - \tau + t < b - \tau + t = d(y,O_{i \bmod 3})\). If \(x = v_{i,a}\) and \(y = v_{j,b}\) where \(i \ne j\) and a < b, then \(d(x,O_l) \ne d(y,O_l)\) for some \(l \ne k\). Therefore, for any different vertices \(x,y \in V(G)\) we have \(r(x|\Omega) \ne r(y|\Omega)\), so \(\Omega\) is a resolving partition of G. \(\square\)

Corollary 2. For \(n \ge 3\) and \(m \ge 2\), if every component of \(mP_n\) has a t-distance vertex, then \(m \le 3 \left\lfloor \frac{n-1}{2} \right\rfloor\).

Proof. By Corollary 1, Lemmas 1 and 2, if \(m \ge 2\) and every component of \(mP_n\) has a t-distance vertex, then we can immediately have \(m \le 3 \left\lfloor \frac{n-1}{2} \right\rfloor\). \(\square\)

In the next lemmas, we give the condition of a disconnected graph G containing paths as components with an even cardinality of middle partition classes.

Lemma 4. For \(m \ge 2\) and \(n_i \ge 4\), let \(G = \bigcup_{i=1}^m P_{n_i}\) and pdd(G) = 3. If there exists \(j \in [1, m]\) where the cardinality of the middle partition class \(M_j\) is 2s, then \(s \le \left\lfloor \frac{n_j - 2}{2} \right\rfloor\).

Proof. Let \(\Omega = \{O_1, O_2, O_3\}\) be a resolving partition of \(G = \bigcup_{i=1}^m P_{n_i}\). Assume there exists a middle partition class \(M_j\) in the \(j^{th}\) component of G such that \(|M_j| = 2s\). Without loss of generality, assume that \(M_j \subset O_2\). If \(n_j\) is even, then \(|M_j| \le n_j - 2\). Thus, \(s \le \frac{n_j - 2}{2} \le \left\lfloor \frac{n_j - 2}{2} \right\rfloor\). Otherwise, \(|M_j| \le n_j - 3\) and \(s \le \frac{n_j - 3}{2} \le \left\lfloor \frac{n_j - 2}{2} \right\rfloor\). \(\square\)

Lemma 5. For \(n \ge 4\) and \(s \in \left[1, \left\lfloor \frac{n-2}{2} \right\rfloor\right]\), there exists a resolving 3-partition of \(3P_n\) such that \(|M_j| = 2s\) for all \(j \in [1,3]\).

Proof. Let \(G = 3P_n\) where \(n \ge 4\), \(V(G) = \{v_{i,j}: 1 \le i \le 3, 1 \le j \le n\}\) and \(E(G) = \{v_{i,j}v_{i,j+1}: 1 \le i \le 3, 1 \le j \le n-1\}\). For every \(s \in \left[1, \left\lfloor \frac{n-2}{2} \right\rfloor \right]\), we define a partition \(\Omega = \{O_1, O_2, O_3\}\) induced by the function \(f_s: V(G) \to \{1, 2, 3\}\), as follows.

\[f_t(v_{i,j}) = \begin{cases} i \mod 3, & j = 1, 2, \dots, \tau, \\ i + 1 \mod 3, & j = \tau + 1, \tau + 2, \dots, \tau + 2s, \\ i + 2 \mod 3, & \text{otherwise,} \end{cases}\] for some \(1 \le \tau \le n - 2s - 1\) where \(f_s(x) = i\) means that \(x \in O_i\). For any \(p \in [1, \tau], q \in [\tau + 1, \tau + 2s]\) and \(r \in [\tau + 2s + 1, n]\), then

\[d(v_{i,p}, O_k) = \begin{cases} 0, & k = i \bmod 3, \\ \tau + 1 - p, & k = i + 1 \bmod 3, \\ \tau + 2s + 1 - p, & \text{otherwise,} \end{cases}\] \[d(v_{i,q}, O_k) = \begin{cases} 0, & k = i + 1 \bmod 3, \\ q - \tau, & k = i \bmod 3, \\ \tau + 2s + 1 - q, & \text{otherwise,} \end{cases}\] \[d(v_{i,r}, O_k) = \begin{cases} 0, & k = i + 2 \bmod 3, \\ r - \tau, & k = i \bmod 3, \\ r - \tau - 2s, & \text{otherwise.} \end{cases}\]

Now, consider two vertices \(x,y \in V(G)\) in \(O_t\) for some \(t \in [1,3]\). If \(x = v_{i,a}\) and \(y = v_{i,b}\) where \(1 \le a < b \le \tau\), then \(d(x,O_{i+1 \bmod 3}) = \tau + 1 - a > \tau + 1 - b = d(y,O_{i+1 \bmod 3})\). If \(x = v_{i,a}\) and \(y = v_{i,b}\) where \(\tau + 1 \le a < b \le \tau + 2s\) or \(\tau + 2s + 1 \le a < b \le n\) then \(d(x,O_{i \bmod 3}) = a - \tau < b - \tau = d(y,O_{i \bmod 3})\). If \(x = v_{i,a}\) and \(y = v_{j,b}\) where \(i \ne j\) and a < b, then \(d(x,O_l) \ne d(y,O_l)\) for some \(l \ne t\). Thus, \(r(x|\Omega) \ne r(y|\Omega)\) for any two different vertices \(x,y \in V(G)\), so \(\Omega\) is a resolving partition of G. \(\square\)

By Lemmas 4 and 5, it is easy to verify this consequence.

Corollary 3. For \(n \ge 4\), if \(pdd(mP_n) = 3\) and the cardinality of every component in the middle partition class is even, then \(m \le 3 \left\lfloor \frac{n-2}{2} \right\rfloor\).

In the following lemma, we give the necessary condition for two components of a graph \(mP_n\) with resolving 3-partition such that the cardinality of their middle partition classes are just different in one vertex.

Lemma 6. Let \(G = \bigcup_{i=1}^{m} P_{n_i}\) and pdd(G) = 3. If there are two components of G having a connected partition such that the difference between both cardinalities of the two middle partition classes is one, then these middle partition classes must be contained in the same partition class.

Proof. Let \(\Omega = \{O_1, O_2, O_3\}\) be a resolving partition of \(G = \bigcup_{i=1}^m P_{n_i}\). Assume there exist two components \(P_{n_i}\) and \(P_{n_j}\) of G having a connected partition of G. Let \(M_i\) and \(M_j\) be the middle partition classes of \(P_{n_i}\) and \(P_{n_j}\), respectively, and \(|M_i| - |M_j| = 1\). Without loss of generality, assume that \(L_i \subset O_1, M_i \subset O_2\) and \(R_i \subset O_3\). Let \(|V(P_{n_i}) \cap L_i| = a\) and \(|V(P_{n_i}) \cap M_i| = b\). Then \(r(v_{i,a}|\Omega) = (0,1,b+1)\), \(r(v_{i,a+1}|\Omega) = (1,0,b)\), \(r(v_{i,a+b}|\Omega) = (b,0,1)\) and \(r(v_{i,a+b+1}|\Omega) = (b+1,1,0)\). Now we consider the partition in \(P_{n_j}\). We assume that \(|M_j| = b - 1\) or \(|M_j| = b + 1\). If \(M_j \subset O_2\), then we can check easily that \(r(x|\Omega) \neq r(y|\Omega)\) for any \(x, y \in V(P_{n_i}) \cup V(P_{n_j})\). Otherwise, we assume \(M_i \subset O_1\) or \(M_i \subset O_3\).

• 1. If \(M_j \subset O_1\) where \(|M_j| = b 1\) or \(|M_j| = b + 1\), then \(r(x|\Omega) = (1,0,b) = r(v_{i,a+1}|\Omega)\) for some \(x \in V(P_{n_j})\) in \(O_2\) or \(r(y|\Omega) = (0,1,b+1) = r(v_{i,a}|\Omega)\) for some \(y \in V(P_{n_j})\) in \(O_1\), respectively, a contradiction.
• 2. If \(M_j \subset O_3\) where \(|M_j| = b 1\) or \(|M_j| = b + 1\), then \(r(x|\Omega) = (b, 0, 1) = r(v_{i,a+b}|\Omega)\) for some \(x \in V(P_{n_j})\) in \(O_2\) or \(r(y|\Omega) = (b+1,1,0) = r(v_{i,a+b+1}|\Omega)\) for some \(y \in V(P_{n_j})\) in \(O_3\), respectively, a contradiction.

Therefore, \(M_i\) and \(M_j\) must be in the same partition class. \(\square\)

2.2 Linear Forest

The following theorem gives the necessary and sufficient conditions for a homogenous linear forest \(G = mP_n\) such that the partition dimension of G is equal to 3.

Theorem 3. For \(n \geq 3\), \(pdd(mP_n) = 3\) if and only if \(2 \leq m \leq 3 \left\lfloor \frac{n-1}{2} \right\rfloor\).

Proof. Let \(G = mP_n\) where \(V(G) = \{v_{i,j} : 1 \le i \le m, 1 \le j \le n\}\), \(E(G) = \{v_{i,j}v_{i,j+1} : 1 \le i \le 3, 1 \le j \le n-1\}\) and \(2 \le m \le 3 \left\lfloor \frac{n-1}{2} \right\rfloor\). By Corollary 1, then \(pdd(G) \ge 3\). Let \(\Omega = \{O_1, O_2, O_3\}\) be a partition of V(G) induced by the function \(f: V(G) \to \{1, 2, 3\}\), as follows.

\[f(v_{i,j}) = \begin{cases} i \mod 3, & j = 1, \\ i + 1 \mod 3, & j = 2, 3, ..., 2 \left[ \frac{i}{3} \right], \\ i + 2 \mod 3, & \text{otherwise.} \end{cases}\]

Note that f(x) = i means that \(x \in O_i\). The vertex \(v_{i, \left[\frac{i}{3}\right] + 1}\) is an \(\left[\frac{i}{3}\right]\)-distance vertex in each \(i^{th}\) component of G, by the definition of the function f. Then we have

\[d(v_{i,1}, O_k) = \begin{cases} 0, & k = i \mod 3, \\ 1, & k = i + 1 \mod 3, \\ 2\left[\frac{i}{3}\right], & \text{otherwise.} \end{cases}\] (1)

For \(q \in \left[2, 2\left[\frac{i}{3}\right]\right]\) and \(r \in \left[2\left[\frac{i}{3}\right] + 1, n\right]\), then

\[d(v_{i,q}, O_k) = \begin{cases} 0, & k = i + 1 \mod 3, \\ q - 1, & k = i \mod 3, \\ 2\left[\frac{i}{3}\right] + 1 - q, & \text{otherwise,} \end{cases}\] (2)

\[d(v_{i,r}, O_k) = \begin{cases} 0, & k = i + 2 \mod 3, \\ r - 1, & k = i \mod 3, \\ r - 2\left\lceil \frac{i}{3} \right\rceil, & \text{otherwise.} \end{cases}\](3)

Let us consider any two vertices \(x, y \in O_t\) for some \(t \in [1,3]\). If \(x = v_{i,a}\) and \(y = v_{i,b}\) for some \(i \in [1,m]\), then \(x, y \in O_{i+1 \bmod 3}\) or \(x, y \in O_{i+2 \bmod 3}\). Note that for a < b, we obtain that \(d(x, O_{i \bmod 3}) = a - 1 < b - 1 = d(y, O_{i \bmod 3})\). Therefore, \(r(x|\Omega) \neq r(y|\Omega)\). Now, we assume that \(x = v_{i,a}\) and \(y = v_{j,b}\) where \(i \neq j\). Since the connected partition induced by f is symmetrical, without loss of generality we can assume that \(x, y \in O_1\). Denote by \(L_i\), \(M_i\) and \(R_i\) the left partition class, the middle partition class and the right partition class in the \(i^{th}\) component of G, respectively. Now, we distinguish three cases.

• 1. If \(x \in L_i\), then \(i \equiv 1 \mod 3\) and \(r(x|\Omega) = (0, 1, 2 \left[\frac{i}{3}\right])\) by Eq. (1).
  • i). If \(y \in L_j\), then \(j \equiv 1 \mod 3\) and \(d(x, O_3) = 2 \left[ \frac{i}{3} \right] \neq 2 \left[ \frac{j}{3} \right] = d(y, O_3)\).
  • ii). If \(y \in M_j\), then \(j \equiv 0 \mod 3\) and \(r(y|\Omega) = (0,2\left\lceil \frac{j}{3}\right\rceil + 1 b, b 1)\) for some \(b \in \left[2,2\left\lceil \frac{j}{3}\right\rceil\right]\) by Eq. (2). If \(b = 2\left\lceil \frac{j}{3}\right\rceil\), then \(d(x,O_3) = 2\left\lceil \frac{i}{3}\right\rceil \neq 2\left\lceil \frac{j}{3}\right\rceil 1 = d(y,O_3)\). Otherwise, \(d(x,O_2) = 1 < 2\left\lceil \frac{j}{3}\right\rceil + 1 b = d(y,O_2)\).

iii). If \(y \in R_j\), then \(j \equiv 2 \mod 3\) and \(r(y|\Omega) = (0, b-1, b-2 \left[\frac{j}{3}\right])\) for some \(b \in \left[2\left[\frac{j}{3}\right] + 1, n\right]\) by Eq. (3). Thus \(d(x, O_2) = 1 < b-1 = d(y, O_2)\).

Therefore, \(r(x|\Omega) \neq r(y|\Omega)\).

• 2. If \(x \in M_i\), then \(i \equiv 0 \mod 3\) and \(r(x|\Omega) = (0,2 \left[\frac{i}{3}\right] + 1 a, a 1)\) for some \(a \in \left[2,2 \left[\frac{i}{3}\right]\right]\) by Eq. (2).
  • i). If \(y \in M_j\), then \(j \equiv 0 \mod 3\) and \(r(y|\Omega) = (0,2\left[\frac{j}{3}\right] + 1 b, b 1)\) for some \(b \in \left[2,2\left[\frac{j}{3}\right]\right]\) by Eq. (2). If a = b, then \(d(x, O_2) = 2\left[\frac{i}{3}\right] + 1 a \neq 2\left[\frac{j}{3}\right] + 1 b = d(y, O_2)\). Otherwise, \(d(x, O_3) = a 1 \neq b 1 = d(y, O_3)\).
  • ii). If \(y \in R_j\), then \(j \equiv 2 \mod 3\) and \(r(y|\Omega) = (0, b-1, b-2\left[\frac{j}{3}\right])\) for some \(b \in \left[2\left[\frac{j}{3}\right] + 1, n\right]\) by Eq. (3). If \(a = b 2\left[\frac{j}{3}\right] + 1\), then \(d(x, O_2) = 2\left[\frac{i}{3}\right] + 1 a = 2\left[\frac{i}{3}\right] b + 2\left[\frac{j}{3}\right] \neq b 1 = d(y, O_2)\). Otherwise, \(d(x, O_3) = a 1 \neq b 2\left[\frac{j}{3}\right] = d(y, O_3)\).

Therefore, \(r(x|\Omega) \neq r(y|\Omega)\).

3. If \(x \in R_i\), then \(i \equiv 2 \mod 3\) and \(r(x|\Omega) = (0, a-1, a-2\left[\frac{i}{3}\right])\) for some \(a \in \left[2\left[\frac{i}{3}\right] + 1, n\right]\) by Eq. (3). If \(y \in R_j\), then \(j \equiv 2 \mod 3\), hence \(r(y|\Omega) = (0, b-1, b-2\left[\frac{j}{3}\right])\) for some \(b \in \left[2\left[\frac{j}{3}\right] + 1, n\right]\). If a = b, then \(d(x, O_3) = a-2\left[\frac{i}{3}\right] \neq b-2\left[\frac{j}{3}\right] = d(y, O_3)\). Otherwise, \(d(x, O_2) = a-1 \neq b-1 = d(y, O_2)\). Therefore, \(r(x|\Omega) \neq r(y|\Omega)\).

This concludes the proof that \(\Omega\) is a resolving partition of \(mP_n\) where \(2 \le m \le 3 \left\lfloor \frac{n-1}{2} \right\rfloor\).

Now we will show that for \(n \geq 3\), if \(G = mP_n\) and pdd(G) = 3, then \(2 \leq m \leq 3 \left \lfloor \frac{n-1}{2} \right \rfloor\). Since G only consists of paths and pdd(G) = 3, then \(m \geq 2\). Let \(\Omega = \{O_1, O_2, O_3\}\) be a resolving partition of G induced by the function \(f: V(G) \to \{1, 2, 3\}\). If every component of G has a connected partition and the cardinality of the middle partition class \(|M_i|\) is odd for all \(i \in [1, m]\), then \(m \leq 3 \left \lfloor \frac{n-1}{2} \right \rfloor\) by Corollary 2. Otherwise, let \(G = G_1 \cup G_2 \cup G_3\) where \(G_i = m_i P_n\), \(i \in [1,3]\), \(m_i \geq 0\) and \(m_1 + m_2 + m_3 = m\), such that:

• 1. All partitions in \(G_1\) and \(G_2\) are connected and the cardinalities of the middle partition classes of \(G_1\) and \(G_2\) are odd and even, respectively.
• 2. There exists a disconnected partition in every component of \(G_3\).

Now, we decompose G into new partition \(\Omega' = \{O'_1, O'_2, O'_3\}\) induced by \(f': V(G) \to \{1, 2, 3\}\) as follows.

• a) For every \(x \in V(G_1)\), we define f'(x) = f(x).
• b) If x is the leftmost vertex of \(M_i\) in \(G_2\), then define \(f'(x) = f(w) + 1 \mod 3\), where w is the left neighbor of x. Otherwise, define \(f'(x) = f(x) + 1 \mod 3\) for every other vertex x in \(G_2\). Note that the cardinality of middle partition class \(M_i'\) in \(G_2\) with respect to \(\Omega'\) is odd for all \(i \in [1, m_2]\). By considering Lemma 6, if there exists \(i \in [1, m_2]\) and \(j \in [1, m_1]\) such that \(||M_i| |M_j|| = 1\) where \(M_i \subset O_a\) and \(M_j \subset O_b\), then a = b. Therefore, if there exists \(i \in [1, m_2]\) and \(j \in [1, m_1]\) such that \(|M_i'| = |M_j'|\) where \(M_i' \subset O_p'\) and \(M_j' \subset O_q'\), then \(p \neq q\) by the definition of f' in \(G_2\). Thus we can verify that any two distinct vertices in \(G_1 \cup G_2\) have distinct representations with respect to \(\Omega'\).
• c) Since all partitions in \(G_3\) are not connected, we can define ordered r-paths \(X_1, X_2, ..., X_r\) in each component of \(G_3\), such that all vertices in \(X_i\) are contained in the same partition class of \(\Omega\). Since \(\Omega\) is a resolving 3-partition, then in each component there will be three consecutive paths \(X_a, X_{a+1}\) and \(X_{a+2}\) in different partition class of \(\Omega\) for some a. Let \(f'(x) = a_1, a_2\) or \(a_3\) where \(\{a_1, a_2, a_3\} = \{1, 2, 3\}\) for all x in \(X_a, X_{a+1}\) or \(X_{a+2}\), respectively. Now, define a new partition \(\Omega_g = \{O_1, O_2, O_3\}\) induced by \(g: X_1 \cup X_2 \cup ... \cup X_r \rightarrow \{1, 2, 3\}\) for each component of \(G_3\), as follows.

\[g(x) = \begin{cases} a_1, & x \in X_i, i \le a, \\ a_2, & x \in X_{a+1}, \\ a_3, & x \in X_i, i \ge a+2. \end{cases}\]

By the new partition \(\Omega_g\), we obtain that every component is connected. Now, define f' in all components in \(G_3\) as follows. If x in the component with odd middle partition, then f'(x) = g(x). Otherwise, define f'(x) as in case (b) above. Therefore, we can have a corresponding partition where all components are connected and have an odd middle partition. Thus \(m \le 3 \left\lfloor \frac{n-1}{2} \right\rfloor\) by Corollary 2. \(\square\)

We give the partition dimension of a graph G consisting of non-homogenous paths in the following theorem.

Theorem 4. For \(m \in \mathbb{N}\), let \(G = \bigcup_{i=1}^{m} P_{n_i}\) where \(n_i \geq 3\) and \(n_i \neq n_j\) for all \(i, j \in [1, m], i \neq j\). Then pdd(G) = 2 if m = 1. Otherwise, pdd(G) = 3.

Proof. If m=1, then \(pdd(G)=pd(P_{n_1})=2\). If \(m\geq 2\), then \(pdd(G)\geq 3\) by Corollary 1. Let \(V(G)=\{v_{i,j}:1\leq i\leq m,1\leq j\leq n_i\}\) where \(n_1< n_2<\cdots< n_m\) and \(\Omega=\{O_1,O_2,O_3\}\) be a partition of V(G) induced by the function \(g\colon V(G)\to\{1,2,3\}\), where g(x)=i means that \(x\in O_i\), as follows.

\[g(v_{i,j}) = \begin{cases} i \mod 3, & j = 1, \\ i + 1 \mod 3, & j = 2, 3, ..., 2 \left\lceil \frac{i}{3} \right\rceil, \\ i + 2 \mod 3, & \text{otherwise.} \end{cases}\]

Since the definition of the function g is the same as the definition of f in the upper bound proof of Theorem 3, then by using a similar argument, any two vertices \(x,y \in V(G)\) in \(O_k\) for \(k \in [1,3]\) have distinct representations with respect to \(\Omega\). \(\square\)

2.3 \(K_3 \cup mP_n\)

In the next theorem we give the necessary and sufficient conditions such that for a graph G consisting of a complete graph of order 3 and paths of order n we have pdd(G) = 3.

Theorem 5. \(pdd(K_3 \cup mP_n) = 3\) if and only if \(n \ge 4\) and \(m \le 3 \left\lfloor \frac{n-2}{2} \right\rfloor\).

Proof. Let \(G = K_3 \cup mP_n\) with the vertex set \(V(G) = V(K_3) \cup V(mP_n) = \{u_t : 1 \le t \le 3\} \cup \{v_{i,j} : 1 \le i \le m, 1 \le j \le n\}, \ n \ge 4 \ \text{and} \ m \le 3 \left\lfloor \frac{n-2}{2} \right\rfloor\). By Corollary 1, then \(pdd(G) \ge 3\). Let \(\Omega = \{O_1, O_2, O_3\}\) be a partition of G induced by the function \(f : V(G) \to \{1, 2, 3\}\), as follows.

\[f(u_t) = t, \text{ for any } 1 \le t \le 3 \text{ and}\] \[f(v_{i,j}) = \begin{cases} i \mod 3, & j = 1, \\ i + 1 \mod 3, & j = 2, 3, ..., 2 \left[ \frac{i}{3} \right] + 1, \\ i + 2 \mod 3, & \text{otherwise.} \end{cases}\]

For \(k \in [1,3]\), \(q \in \left[2,2\left[\frac{i}{3}\right]+1\right]\) and \(r \in \left[2\left[\frac{i}{3}\right]+2,n\right]\), then

\[d(u_t, O_k) = \begin{cases} 0, & k = t \\ 1, & \text{otherwise,} \end{cases}\]

\[d(v_{i,1}, O_k) = \begin{cases} 0, & k = i \mod 3, \\ 1, & k = i + 1 \mod 3, \\ 2\left[\frac{i}{3}\right] + 1, & \text{otherwise,} \end{cases}\] (4)

\[d(v_{i,q}, O_k) = \begin{cases} 0, & k = i + 1 \mod 3, \\ q - 1, & k = i \mod 3, \\ 2\left[\frac{i}{3}\right] + 2 - q, & \text{otherwise,} \end{cases}\] (5)

\[d(v_{i,r}, O_k) = \begin{cases} 0, & k = i + 2 \mod 3, \\ r - 1, & k = i \mod 3, \\ r - 2\left[\frac{i}{3}\right] - 1, & \text{otherwise.} \end{cases}\] (6)

Now, we consider two distinct vertices \(x, y \in V(G)\) in the same partition class of \(\Omega\). If \(x = u_t\) and \(y = v_{i,j}\), then \(d(x, O_k) = 1 < d(y, O_k)\) for some \(k \neq t\). Thus we obtain \(r(x|\Omega) \neq r(y|\Omega)\) for every \(1 \leq t \leq 3, 1 \leq i \leq m\) and \(1 \leq j \leq n\). For two vertices \(x, y \in V(mP_n)\), we can verify that \(r(x|\Omega) \neq r(y|\Omega)\) similarly as in the proof of Theorem 3. Therefore, \(\Omega\) is a resolving partition of G.

To prove the converse, let \(G = K_3 \cup mP_n\) and pdd(G) = 3. By Theorem 2, since any vertex of \(K_3\) is a 1-distance vertex, while a vertex \(x \in V(mP_n)\) is also a 1-distance vertex for n = 3, then \(n \ge 4\). To prove that \(m \le 3 \left\lfloor \frac{n-2}{2} \right\rfloor\), let \(\Omega = \{O_1, O_2, O_3\}\) be a partition of G induced by the function \(f: V(G) \to \{1, 2, 3\}\). We consider the components of \(mP_n\). If all partitions of \(V(mP_n)\) under \(\Omega\) are connected and have an even middle partition in each component, then \(m \le 3 \left\lfloor \frac{n-2}{2} \right\rfloor\) by Corollary 3. Otherwise, let \(G = G_1 \cup G_2 \cup G_3\) where \(G_i = m_i P_n\), \(i \in [1,3]\), \(m_i \ge 0\) and \(m_1 + m_2 + m_3 = m\), such that:

• 1. All partitions in \(G_1\) and \(G_2\) are connected and the cardinalities of the middle partition classes of \(G_1\) and \(G_2\) are even and odd, respectively.
• 2. There exists a disconnected partition in every component of \(G_3\).

Now, we decompose G into partition \(\Omega' = \{O'_1, O'_2, O'_3\}\) induced by \(f': V(G) \to \{1, 2, 3\}\) as in the proof of Theorem 3. In this case, by a similar method used in the proof of Theorem 3, we can redefine the partition f such that all components have a connected partition class with even cardinality of the middle partition. Thus, \(m \le 3 \left| \frac{n-2}{2} \right|\) by Corollary 3.

Since every vertex in \(K_3\) is a 1-distance vertex, then we cannot have \(|M_i'| = 1\) for any \(i \in [1, m]\). Hence, if we define a partition \(\Omega'\) such that \(|M_i'|\) is odd for all \(i \in [1, m]\), then we obtain that \(m \le 3 \left| \frac{n-1}{2} \right| - 3 \le 3 \left| \frac{n-2}{2} \right|\). \(\square\)

Acknowledgements

This research was supported by a research grant from the PMDSU DIKTI Program of the Ministry of Research, Technology and Higher Education, Indonesia.