The connected partition dimension of truncated wheels

Abstract

Let G be a connected graph. For a vertex v of G and a subset S of V(G), the distance between v and S is d(v, S) = min$\{d(v,x),x\in S\}.$ Given an ordered k-partition $\Pi$=$\{S_1,S_2,\dots ,S_k\}$ of V(G), the representation of v with respect to $\Pi$ is the k-vector $r(v|\Pi )=(d(v,S_1),d(v,S_2),\dots ,d(v,S_k)).$ If $r(u|\Pi )\ne r(v|\Pi )$ for each pair of distinct vertices $u,v\in V(G),$ then the k-partition $\Pi$ is said to be a resolving partition. The partition dimension of G, denoted by pd(G), is determined by the minimum k for which there is a resolving partition of V(G). If each induced subgraph $〈S_i〉$ for S_i, $1\le i\le k,$ is connected in G, then the resolving partition $\Pi$=$\{S_1,S_2,\dots ,S_k\}$ of V(G) is said to be connected. The connected partition dimension of G, denoted by cpd(G), is determined by the minimum k for which there is a connected resolving partition of V(G). In this paper, we compute the connected partition dimension of the truncated wheels TW_n. It is shown that for any natural number $n\ge 3,$ the connected partition dimension of the truncated wheel TW_n is 3 when n = 3 and $\lceil n/3\rceil +1$ when $n\ge 4.$

Keywords:

• Partite set
• resolving partition
• connected partition dimension

1. Introduction and background

Let G be a connected graph and let S be a nonempty subset of V(G). The distance between a vertex $v\in V(G)$ and S, denoted by d(v, S), is defined as $d(v,S)=\text{min}\{d(v,s)|s\in S\}.$ Let $\Pi =\{S_1,S_2,S_3,\dots ,S_k\}$ be an ordered k-partition of V(G). The representation of $v\in V(G)$ with respect to $\Pi$ is defined to be the k-vector $r(v|\Pi )=(d(v,S_1),d(v,S_2),\dots ,d(v,S_k)).$ The partition $\Pi$ is called a resolving partition of G if $r(w|\Pi )\ne r(v|\Pi )$ for all distinct $w,v\in V(G).$ The partition dimension of a graph G is the cardinality of a minimum resolving partition of G, denoted by pd(G). This concept was introduced by Chartrand, Salehi and Zhang [2] and proved that if G is a connected graph of order $n\ge 2,$ pd(G) = 2 if and only if G = P_n and pd(G) = n if and only if G = K_n.

If each subgraph $〈S_i〉$ induced by S_i ($1\le i\le k$) is connected in G, then the resolving partition $\Pi =\{S_1,S_2,S_3,\dots ,S_k\}$ of V(G) is said to be connected. The minimum k for which there is a connected resolving k-partition of V(G) is the connected partition dimension of G, denoted by cpd(G). This variation was introduced by Saenpholphat and Zhang [4]. They also proved that if G is a connected graph of order $n\ge 2,$ cpd(G) = 2 if and only if G = P_n and cpd(G) = n if and only if G = K_n. Saenpholphat and Zhang noted that every connected resolving partition of a connected graph is a resolving partition and showed that the converse, in general, is not true. Thus, if G is a connected graph of order $n\ge 2,$ then $2\le pd(G)\le \mathit{cpd}(G)\le n.$ As a consequence, if G is a connected graph of order $n\ge 3$ that is not a path, then $\mathit{cpd}(G)\ge 3.$

In this paper, we compute the connected partition dimension of a wheel related graph called truncated wheels defined by Garces and Rosario [3] as follows: Let $n\ge 3$ be an integer. A truncated wheel, denoted by TW_n, is the graph with vertex set $V(T{W}_n)=\left\{a\right\}$ $\cup$ B $\cup$ C, where $B=\{b_i:1\le i\le n\}$ and $C=\{c_{i,j}:1\le i\le n,1\le j\le 2\}$ and edge set $E(T{W}_n)=\{a{b}_i:1\le i\le n\}$ $\cup$ $\{b_i{c}_{i,j}:1\le i\le n,1\le j\le 2\}$ $\cup$ $\{c_{i,1}{c}_{i,2}:$ $1\le i\le n\}$ $\cup$ $\{c_{i,2}{c}_{i+1,1}:1\le i\le n\},$ where $c_{n+1,1}=c_{1,1}.$ For other graph theory notation and terminology not defined in this paper, we refer to the book of Bondy and Murty [1].

2. The main results

We first note that the truncated wheel TW_n is of order $3n+1$ and is not path for each $n\ge 3.$ This implies that $\mathit{cpd}(T{W}_n)\ge 3.$ We also note that $\mathit{diam}(T{W}_n)=4$ for all $n\ge 4.$

Proposition 2.1.

For each integer n, $3\le n\le 6,\mathit{cpd}(T{W}_n)=3.$

Proof.

To prove that cpd$(T{W}_n)=3$ for $3\le n\le 6,$ it is enough to show a connected resolving partition of $V(T{W}_n)$ with cardinality 3 for each n.

Let $\Pi$ = $\left\{S_1,S_2,S_3\right\}$ be a partition of $V(T{W}_n).$ For n = 3, we let $S_1=\{a,b_3,c_{3,2}\},S_2=\{b_1,b_2,c_{1,1},c_{1,2},c_{2,1}\},$ and $S_3=\{c_{3,1},c_{2,2}\}.$ The representations of the vertices of TW₃ with respect to $\Pi$ are as follows: $$\begin{array}{c}r(a|\Pi )=(0,1,2),r(b_1|\Pi )=(1,0,3),r(b_2|\Pi )=(1,0,1),\\ r(b_3|\Pi )=(0,2,1),r(c_{1,1}|\Pi )=(1,0,2),r(c_{1,2}|\Pi )=(2,0,2),\\ r(c_{2,1}|\Pi )=(2,0,1),r(c_{2,2}|\Pi )=(2,1,0),r(c_{3,1}|\Pi )=(1,2,0),\\ r(c_{3,2}|\Pi )=(0,1,1).\end{array}$$

For n = 4, we let $S_1=\{a,b_4,c_{4,1},c_{4,2}\},S_2=\{b_1,b_2,c_{1,1},c_{1,2},c_{2,1}\},$ and $S_3=\{b_3,c_{2,2},c_{3,1},c_{3,2}\}.$ The representations of the vertices of TW₄ with respect to $\Pi$ are as follows: $$\begin{array}{c}r(a|\Pi )=(0,1,1),r(b_1|\Pi )=(1,0,2),r(b_2|\Pi )=(1,0,1),\\ r(b_3|\Pi )=(1,2,0),r(b_4|\Pi )=(0,2,2),r(c_{1,1}|\Pi )=(1,0,3),\\ r(c_{1,2}|\Pi )=(2,0,2),r(c_{2,1}|\Pi )=(2,0,1),r(c_{2,2}|\Pi )=(2,1,0),\\ r(c_{3,1}|\Pi )=(2,2,0),r(c_{3,2}|\Pi )=(2,3,0),r(c_{4,1}|\Pi )=(0,2,1),\\ r(c_{4,2}|\Pi )=(0,1,2).\end{array}$$

For n = 5, we let $S_1=\{a,b_3,b_4,b_5,c_{3,2},c_{4,1},c_{4,2},c_{5,1}\},S_2=\{b_1,c_{1,1},c_{1,2},c_{2,1},c_{5,2}\},$ and $S_3=\{b_2,c_{2,2},c_{3,1}\}.$ The representations of the vertices of TW₅ with respect to $\Pi$ are as follows: $$\begin{array}{c}r(a|\Pi )=(0,1,1),r(b_1|\Pi )=(1,0,2),r(b_2|\Pi )=(1,1,0),\\ r(b_3|\Pi )=(0,2,1),r(b_4|\Pi )=(0,2,2),r(b_5|\Pi )=(0,1,2),\\ r(c_{1,1}|\Pi )=(2,0,3),r(c_{1,2}|\Pi )=(2,0,2),r(c_{2,1}|\Pi )=(2,0,1),\\ r(c_{2,2}|\Pi )=(2,1,0),r(c_{3,1}|\Pi )=(1,2,0),r(c_{3,2}|\Pi )=(0,3,1),\\ r(c_{4,1}|\Pi )=(0,3,2),r(c_{4,2}|\Pi )=(0,2,3),r(c_{5,1}|\Pi )=(0,1,3),\\ r(c_{5,2}|\Pi )=(1,0,3).\end{array}$$

For n = 6, we let $S_1=\{a,b_1,b_5,b_6,c_{1,1},c_{5,2},c_{6,1},c_{6,2}\},S_2=\{b_2,c_{1,2},c_{2,1},c_{2,2},c_{3,1}\},$ and $S_3=\{b_3,b_4,c_{3,2},c_{4,1},c_{4,2},c_{5,1}\}.$ The representations of the vertices of TW₆ with respect to $\Pi$ are as follows: $$\begin{array}{c}r(a|\Pi )=(0,1,1),r(b_1|\Pi )=(0,1,2),r(b_2|\Pi )=(1,0,2),\\ r(b_3|\Pi )=(1,1,0),r(b_4|\Pi )=(1,2,0),r(b_5|\Pi )=(0,2,1),\\ r(b_6|\Pi )=(0,2,2),r(c_{1,1}|\Pi )=(0,1,3),r(c_{1,2}|\Pi )=(1,0,3),\\ r(c_{2,1}|\Pi )=(2,0,3),r(c_{2,2}|\Pi )=(2,0,2),r(c_{3,1}|\Pi )=(2,0,1),\\ r(c_{3,2}|\Pi )=(2,1,0),r(c_{4,1}|\Pi )=(2,2,0),r(c_{4,2}|\Pi )=(2,3,0),\\ r(c_{5,1}|\Pi )=(1,3,0),r(c_{5,2}|\Pi )=(0,3,1),r(c_{6,1}|\Pi )=(0,3,2),\\ r(c_{6,2}|\Pi )=(0,2,3).\end{array}$$

Clearly, the representations are distinct and it can be easily checked that the induced subgraph for any partite set is connected in TW_n for each n, $n=3,4,5,6.$ Thus, $\Pi$ is a connected resolving partition of $V(T{W}_n).$ Therefore, the proposition holds. □

Lemma 2.2.

Let $n\ge 7$ be an integer. If $\Pi$ = $\left\{S_1,S_2,S_3\right\}$ is a connected resolving partition of $V(T{W}_n)$, then $1\le \left|S_i\right|\le 16$ for each $i,i=1,2,3.$

Proof.

Suppose, on the contrary, that one partite set, say S₁, has more than 16 elements; that is, $\left|S_1\right|\ge 17.$ Since diam$(T{W}_n)$ = 4, $1\le d(v,S_2)\le 4$ and $1\le d(v,S_3)\le 4$ for each $v\in S_1.$ This implies that given $y=d(v,S_2)$ and $z=d(v,S_3),r(v|\Pi )$ $\in D_1=\{(0,y,z):1\le y\le 4,1\le z\le 4\}.$ By the fundamental counting principle, $\left|D_1\right|$ = 16. Since $\left|S_1\right|\ge 17,$ by the pigeonhole principle, there exist two vertices of S₁ having the same representation with respect to $\Pi .$ This contradicts the assumption that $\Pi$ is a connected resolving partition of $V(T{W}_n).$ Therefore, $1\le \left|S_i\right|\le 16$ for each i. □

Lemma 2.3.

If $\Pi =\{S_1,S_2,S_3\}$ is a connected resolving partition of $V(T{W}_7)$ with $\left|S_3\right|\le \left|S_2\right|\le \left|S_1\right|$, then $8\le \left|S_1\right|\le 16,3\le \left|S_2\right|\le 10$, and $1\le \left|S_3\right|\le 7.$

Proof.

Let $\Pi =\{S_1,S_2,S_3\}$ be a connected resolving partition of $V(T{W}_7).$ By Lemma 2.2, $1\le \left|S_i\right|\le 16$ for each i = 1, 2, 3. Since $\left|S_3\right|\le \left|S_2\right|\le \left|S_1\right|,$ then, by exhausting all possible cardinalities of S_i as shown in Table 1, we conclude that $8\le \left|S_1\right|\le 16,3\le \left|S_2\right|\le 10,$ and $1\le \left|S_3\right|\le 7.$ □

Table 1. Possible cardinalities of S₁, S₂, and S₃ with $\left|S_3\right|\le \left|S_2\right|\le \left|S_1\right|.$

${\mathbf{S}}_{\mathbf{1}}$	${\mathbf{S}}_{\mathbf{2}}$	${\mathbf{S}}_{\mathbf{3}}$	${\mathbf{S}}_{\mathbf{1}}$	${\mathbf{S}}_{\mathbf{2}}$	${\mathbf{S}}_{\mathbf{3}}$	${\mathbf{S}}_{\mathbf{1}}$	${\mathbf{S}}_{\mathbf{2}}$	${\mathbf{S}}_{\mathbf{3}}$	${\mathbf{S}}_{\mathbf{1}}$	${\mathbf{S}}_{\mathbf{2}}$	${\mathbf{S}}_{\mathbf{3}}$	${\mathbf{S}}_{\mathbf{1}}$	${\mathbf{S}}_{\mathbf{2}}$	${\mathbf{S}}_{\mathbf{3}}$	${\mathbf{S}}_{\mathbf{1}}$	${\mathbf{S}}_{\mathbf{2}}$	${\mathbf{S}}_{\mathbf{3}}$
16	5	1	14	7	1	13	6	3	12	5	5	10	10	2	9	8	5
16	4	2	14	6	2	13	5	4	11	10	1	10	9	3	9	7	6
16	3	3	14	5	3	12	9	1	11	9	2	10	8	4	8	8	6
15	6	1	14	4	4	12	8	2	11	8	3	10	7	5	8	7	7
15	5	2	13	8	1	12	7	3	11	7	4	10	6	6
15	4	3	13	7	2	12	6	4	11	6	5	9	9	4

Proposition 2.4.

The connected partition dimension of TW₇ is 4.

Proof.

Let $\Pi =\{S_1,S_2,S_3,S_4\}$ be a partition of $V(T{W}_7),$ where $S_1=\left\{a\right\}\cup B,S_2=\{c_{1,1},c_{1,2},c_{2,1},c_{2,2},c_{3,1},c_{3,2}\},S_3=\{c_{4,1},c_{4,2},c_{5,1},c_{5,2},c_{6,1},c_{6,2}\},$ and $S_4=\{c_{7,1},c_{7,2}\}.$ It is straightforward to verify that each induced subgraph $〈S_i〉$ for $S_i,i=1,2,3,4,$ is connected in TW₇. One can also verify that any two vertices in the same partite set have distinct representations with respect to $\Pi .$ Thus, we only need to prove that cpd$(T{W}_7)\ge 4$ by showing that there exists no connected resolving partition of $V(T{W}_7)$ with cardinality 3.

Suppose $\Pi \prime =\{S{\prime }_1,S{\prime }_2,S{\prime }_3\}$ is a connected resolving partition of $V(T{W}_7).$ We can assume, without loss of generality, that $\left|S{\prime }_3\right|\le \left|S{\prime }_2\right|\le \left|S{\prime }_1\right|.$ Then, by Lemma 2.3, we have $8\le \left|S{\prime }_1\right|\le 16,;3\le \left|S{\prime }_2\right|\le 10,$ and $1\le \left|S{\prime }_3\right|\le 7.$ Moreover, given that diam$(T{W}_7)$ = 4, we have $1\le d(v,S{\prime }_j)\le 4$ for all $v\in S{\prime }_i,1\le i,j\le 3,i\ne j.$ We consider two cases. From here onwards, we let $B\prime$ and $B″$ be nonempty subsets of B and $C\prime$ and $C″$ be nonempty subsets of C.

Case 1. $1\le \left|S{\prime }_3\right|\le 6$ and $9\le \left|S{\prime }_1\right|\le 16$

Subcase 1.1. $a\in S{\prime }_3$

In this case, we have $1\le d(v,S{\prime }_2)\le 4$ and $1\le d(v,S{\prime }_3)\le 2$ for all $v\in S_1.$ Thus, $r(v|\Pi \prime )\in D_2=\{(0,y,z):1\le y\le 4,1\le z\le 2\},$ where $y=d(v,S{\prime }_2)$ and $z=d(v,S{\prime }_3).$ By the fundamental counting principle, we have $\left|D_2\right|$ = 8. Since $9\le \left|S{\prime }_1\right|\le 16,$ by the pigeonhole principle, there exist two vertices of $S{\prime }_1$ having the same representation with respect to $\Pi \prime .$

Subcase 1.2. $S{\prime }_3=B\prime$ or $S{\prime }_3=B\prime \cup C\prime$

If $a\in S{\prime }_2,$ then $1\le d(v,S{\prime }_2)\le 2$ and $1\le d(v,S{\prime }_3)\le 3$ for all $v\in S{\prime }_1.$ Thus, $r(v|\Pi \prime )\in D_3=\{(0,y,z):1\le y\le 2,1\le z\le 3\},$ where $y=d(v,S{\prime }_2)$ and $z=d(v,S{\prime }_3).$ By the fundamental counting principle, we have $\left|D_3\right|$ = 6. Since $9\le \left|S{\prime }_1\right|\le 16,$ by the pigeonhole principle, there exist two vertices of $S{\prime }_1$ having the same representation with respect to $\Pi \prime .$ On the other hand, if $a\in S{\prime }_1,$ then $S{\prime }_1$ must contain at least two vertices in $B⃥B\prime ,$ otherwise the vertices of $S{\prime }_2$ are disconnected. In this case, there exist two vertices $b_i,b_{i\prime }\in S{\prime }_1$ with $r(b_i|\Pi \prime )=r(b_{i\prime }|\Pi \prime ).$

Subcase 1.3. $S{\prime }_3=C\prime$

If $a\in S{\prime }_2,$ then $1\le d(v,S{\prime }_2)\le 2$ and $1\le d(v,S{\prime }_3)\le 4$ for all $v\in S{\prime }_1.$ Thus, $r(v|\Pi \prime )\in D_4=\{(0,y,z):1\le y\le 2,1\le z\le 4\},$ where $y=d(v,S_2)$ and $z=d(v,S_3).$ By the fundamental counting principle, we have $\left|D_4\right|$ = 8. Since $9\le \left|S{\prime }_1\right|\le 16,$ by the pigeonhole principle, there exist two vertices of $S{\prime }_1$ having the same representation with respect to $\Pi \prime .$ On the other hand, if $a\in S{\prime }_1,$ then $S{\prime }_1$ must contain at least three vertices in B, otherwise the vertices of $S{\prime }_2$ are disconnected. In this case, there exist two vertices $b_i,b_{i\prime }\in S{\prime }_1$ with $r(b_i|\Pi \prime )=r(b_{i\prime }|\Pi \prime ).$

Case 2. $6\le \left|S{\prime }_3\right|\le 7$ and $\left|S{\prime }_1\right|=8$

Subcase 2.1. $a\in S{\prime }_3$

In this case, it can be verified that $S{\prime }_1$ (or $S{\prime }_3$) contains two vertices $b_i,b_{i\prime }\in B$ with $r(b_i|\Pi \prime )=r(b_{i\prime }|\Pi \prime ).$

Subcase 2.2. $S{\prime }_3=B\prime \cup C\prime$

If $a\in S{\prime }_2,$ then $1\le d(v,S{\prime }_2)\le 2$ and $1\le d(v,S{\prime }_3)\le 3$ for all $v\in S{\prime }_1.$ Thus, $r(v|\Pi \prime )\in D_5=\{(0,y,z):1\le y\le 2,1\le z\le 3\},$ where $y=d(v,S{\prime }_2)$ and $z=d(v,S{\prime }_3).$ By the fundamental counting principle, we have $\left|D_5\right|$ = 6. Since $\left|S{\prime }_1\right|=8,$ then by the pigeonhole principle, there exist two vertices of S₁ having the same representation with respect to $\Pi \prime .$ On the other hand, if $a\in S{\prime }_1,$ then $S{\prime }_1$ must contain at least two vertices in $B⃥B\prime ,$ otherwise the vertices of $S{\prime }_2$ are disconnected. In this case, there exist two vertices $b_i,b_{i\prime }\in S{\prime }_1$ with $r(b_i|\Pi \prime )=r(b_{i\prime }|\Pi \prime ).$

Subcase 2.3. $S{\prime }_3=C\prime$

If $a\in S{\prime }_2,$ then $S{\prime }_1=C″,$ with $C″\cap C\prime =\varnothing$ or $S{\prime }_1=B″\cup C″.$ If $S{\prime }_1=C″,$ then $d(v,S{\prime }_2)=1$ and $1\le d(v,S{\prime }_3)\le 4$ for all $v\in S{\prime }_1.$ Thus, $r(v|\Pi \prime )\in D_6=\{(0,1,z):1\le z\le 4\},$ where $z=d(v,S{\prime }_3).$ By the fundamental counting principle, we have $\left|D_6\right|$ = 4. Since $\left|S{\prime }_1\right|=8,$ by the pigeonhole principle, there exist two vertices of $S{\prime }_1$ having the same representation with respect to $\Pi \prime .$ If $S{\prime }_1=B″\cup C″,$ then $S{\prime }_2$ must contain at least two vertices in $B\backslash B″,$ otherwise the vertices of $S{\prime }_1$ are disconnected. In this case, there exist two vertices $b_{i_2},b_{i{\prime }_2}\in S{\prime }_2$ with $r(b_{i_2}|\Pi \prime )=r(b_{i{\prime }_2}|\Pi \prime ).$ On the other hand, if $a\in S{\prime }_1,$ then $S{\prime }_1$ must contain at least four vertices in B, otherwise the vertices of S₂ are disconnected. In this case, there exist two vertices $b_{i_1},b_{i{\prime }_1}\in S{\prime }_1$ with $r(b_{i_1}|\Pi \prime )=r(b_{i{\prime }_1}|\Pi \prime ).$

In all cases and subcases, there exist two vertices having the same representation with respect to $\Pi \prime .$ This contradicts the assumption that $\Pi \prime$ is a connected resolving partition of $V(T{W}_7).$ Thus, we have $\mathit{cpd}(T{W}_7)\ge 4$ and the proposition holds. □

Proposition 2.5.

Let $n\ge 8$ be an integer. Then, $\mathit{cpd}(T{W}_n)\le \lceil n/3\rceil +1.$

Proof.

To prove this, it is enough to show a connected resolving partition of $V(T{W}_n)$ with cardinality $\lceil n/3\rceil +1$ for $n\ge 8,$ where $\lceil x\rceil$ denotes the smallest integer greater than or equal to x. Let $\alpha =\lceil n/3\rceil$ and let $\Pi =\{S_0,S_1,S_2,\dots ,S_{\alpha -1},S_{\alpha }\}$ be a partition of $V(T{W}_n).$ We consider three cases.

Case 1. $n\equiv 2\mathrm{ }\text{mod}\mathrm{ }3$

If $n\equiv 2\mathrm{ }\text{mod}\mathrm{ }3,$ we can let $S_i=\{c_{3i-2,1},c_{3i-2,2},c_{3i-1,1},c_{3i-1,2},c_{3i,1},c_{3i,2}\}$ for $1\le i\le \alpha -1,S_{\alpha }=\{c_{3\alpha -2,1},c_{3\alpha -2,2},c_{3\alpha -1,1},c_{3\alpha -1,2}\},$ and $S_0=\left\{a\right\}\cup B.$

Case 2. $n\equiv 0\mathrm{ }\text{mod}\mathrm{ }3$

If $n\equiv 0\mathrm{ }\text{mod}\mathrm{ }3,$ we can let $S_i=\{c_{3i-2,1},c_{3i-2,2},c_{3i-1,1},c_{3i-1,2},c_{3i,1},c_{3i,2}\}$ for $1\le i\le \alpha$ and $S_0=\left\{a\right\}\cup B.$

Case 3. $n\equiv 1\mathrm{ }\text{mod}\mathrm{ }3$

If $n\equiv 1\mathrm{ }\text{mod}\mathrm{ }3,$ we can let $S_i=\{c_{3i-2,1},c_{3i-2,2},c_{3i-1,1},c_{3i-1,2},c_{3i,1},c_{3i,2}\}$ for $1\le i\le \alpha -1,S_{\alpha }=\{c_{3\alpha -2,1},c_{3\alpha -2,2}\}$ and $S_0=\left\{a\right\}\cup B.$

It is straightforward to verify that the vertices in the same partite set in each case have distinct representations with respect to $\Pi$ and the partite sets induced connected subgraphs. Therefore, $\mathit{cpd}(T{W}_n)\le \lceil n/3\rceil +1.$ □

Lemma 2.6.

Let n and m be integers with $n\ge 8$ and $3\le m\le \lceil n/3\rceil$. Then, $2n/m\ge 5.$

Proof.

Observe that $2n/3>5$ for all $n\ge 8.$ To prove the lemma, it suffices to show that $2n/m\ge 5,$ where $m=\lceil n/3\rceil .$ We consider three cases.

Case 1. $n=3k+2,$ where $k\ge 2$

In this case, $k=(n-2)/3$ and $\lceil n/3\rceil =\lceil (3k+2)/3\rceil =k+1=[(n-2)/3]+1=(n+1)/3.$ Hence, $2n/\lceil n/3\rceil =2n/[(n+1)/3]=6n/(n+1)=(6n+6-6)/(n+1)=[6(n+1)-6]/(n+1)=6-[6/(n+1)]>5.$

Case 2. $n=3k,$ where $k\ge 3$

In this case, $\lceil n/3\rceil =\lceil k\rceil =k.$ Therefore, $2n/\lceil n/3\rceil =[2(3k)]/k=6.$

Case 3. $n=3k+1,$ where $k\ge 3$

In this case, $k=(n-1)/3$ and $\lceil n/3\rceil =\lceil (3k+1)/3\rceil =k+1=[(n-1)/3]+1=(n+2)/3.$ Hence, $2n/\lceil n/3\rceil =2n/[(n+2)/3]=6n/(n+2)=[6(n+2)-12]/(n+2)=6-[12/(n+2)]\ge 5.$

In all cases, it is verified that $2n/m\ge 5.$ Therefore, the conclusion holds. □

Proposition 2.7.

Let $n\ge 8$ be an integer. Then $\mathit{cpd}(T{W}_n)\ge \lceil n/3\rceil +1.$

Proof.

To prove this, it is enough to show that there exists no connected resolving partition of $V(T{W}_n)$ with cardinality m, where $3\le m\le \lceil n/3\rceil .$

Suppose, on the contrary, that there exists a connected resolving partition $\Pi$=$\{S_1,S_2,\dots ,S_m\}$ of $V(T{W}_n).$ By Lemma 2.6, $2n/m\ge 5$ for all values of n and m. This implies that there exist at least two distinct partite sets, say S_k and $S_k^{\prime },1\le k,k\prime \le m,$ such that both $〈S_k〉$ and $〈S_k^{\prime }〉$ contain a path in C with cardinality at least 5. This further implies that $〈S_k〉$ has a subpath $c_{i,1}-c_{i+1,2}$ for some i and $〈S_k^{\prime }〉$ has a subpath $c_{i\prime ,1}-c_{i\prime +1,2}$ for some $i\prime .$

If $a\in S_k$ (or $S_k^{\prime }$), then S_k (or $S_k^{\prime }$) must contain at least two vertices b_i, $b_{i+1}\in B,$ otherwise the vertices of S_k (or $S_k^{\prime }$) are disconnected. In this case, we have that $r(b_i|\Pi )=r(b_{i+1}|\Pi ).$ On the other hand, if $a\notin S_k$ (or $S_k^{\prime }$), then the partite set containing a must also contain at least two vertices $b_{i\prime },b_{i\prime +1}\in B,$ otherwise its vertices are disconnected. In this case, we have that $r(b_{i\prime }|\Pi )=r(b_{i\prime +1}|\Pi ).$

In any case, there exist two vertices having the same representation with respect to $\Pi .$ This contradicts the assumption that $\Pi$ is a connected resolving partition of $V(T{W}_n).$ Therefore, we conclude that there exists no connected resolving partition with cardinality m, where $3\le m\le \lceil n/3\rceil .$ □

By Propositions 2.1, 2.4, 2.5 and 2.7, we have the main result as presented in the next theorem.

Theorem 2.8.

Let $n\ge 3.$ Then, $$\mathit{cpd}(T{W}_n)=\{\begin{array}{cc}3\hfill & if\mathrm{ }n=3\hfill \\ \lceil n/3\rceil +1\hfill & if\mathrm{ }n\ge 4.\hfill \end{array}$$