Partition dimension of trees - palm approach

Yusuf Hafidh^a , Edy Tri Baskoroa,b

^aCombinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Indonesia

emails: yusuf.hafidh@itb.ac.id, ebaskoro@itb.ac.id

The partition dimension of a graph is the minimum number of vertex partitions such that every vertex has different distances to the ordered partitions. Many resolving partitions for trees have all vertices not in an end-path in the same partition. This reduces the problem of the partition dimension of trees into finding the partition dimension of palms, the end-paths from a branch. In this paper, we construct a resolving partition for trees using resolving partitions of their palms. We also study some bounds for the partition dimension of palms and also find the partition dimension of regular palm and olive trees.

Keywords: partition dimension, tree, palm Mathematics Subject Classification: 05C12, 05C15

DOI: 10.5614/ejgta.2024.12.2.7

1. Introduction

Let G = (V, E) be a simple connected graph. A partition Π = {S1, S2, . . . , Sk} of the vertexset V is called a resolving partition if for every two vertices, there exists a partition class Sⁱ ∈ Π with different distances to the two vertices, we say that this partition revolves the two vertices. To show Π is a resolving partition, it suffices to verify that vertices in the same partition are resolved. The partition dimension of G, denoted by pd(G), is the minimum number of partitions in a resolving partition of G. The representation of a vertex v with respect to teh ordered partition Π

Received: 28 November 2022, Revised: 10 June 2024, Accepted: 21 July 2024.

^bCenter for Research Collaboration on Graph Theory and Combinatorics, Indonesia

is given by r(v|Π) = (d(v, S1), d(v, S2), . . . , d(v, Sk)). Note that a resolving partition is equivalent to every vertex having different representations.

Several methods have been developed to construct a resolving partition of a tree graph, see [6, 12, 13]. Many constructions focus on vertices in the end-paths, a path joining a leaf to its nearest branch, with vertices not in an end-path in the same partition class. These constructions make us believe that obtaining the partition dimension of palms, the union of all end-paths from a branch, will help obtain a better resolving partition for trees. We strengthen this observation by giving an upper bound for the partition dimension of trees using the partition dimension of their palms in the next section.

In our previous paper, we utilize the locating-coloring of palms to generate a locating-coloring of trees, see [10]. In this paper, we will do a similar approach for the partition dimension of trees. The partition construction for trees and especially for palms we provide in this paper differs from the locating coloring used in [10]. Other different constructions were also proposed for computing partition dimensions of graphs, see [1] and [11].

A star Sⁿ is the complete bipartite graph K1,n. A palm Sn(a1, a2, . . . , an) for n ≥ 2, is a graph obtained from a star Sⁿ by subdividing the i th edge aⁱ − 1 times. Since permuting aⁱ will result in an isomorphic graph, we always consider {ai} in a non-decreasing sequence. Let us denote the vertex and edge set of a palm by

\[V = \{a_0\} \cup \{a_{i,j} \mid 1 \le i \le n, 1 \le j \le a_i\}, \text{ and } E = \{a_0 a_{i,1} \mid 1 \le i \le n\} \cup \{a_{i,j} a_{i,j+1} \mid 1 \le i \le n, 1 \le j \le a_i - 1\}.\]

The k th level is the set of vertices of distance k to the hub vertex a0, and the k th end-path is the subgraph induced by the set {a0} ∪ {ak,j : 1 ≤ j ≤ ak}. A palm is called an end-palm if it is the union of all end-paths from a branch.

If aⁱ = i for every i then this palm tree is called an olive tree and denoted by On, namely Oⁿ = Sn(1, 2, . . . , n). Olive trees with partition dimensions 3 and 4 were studied in [2] and [8]. Figure 1 is an example of an olive tree O5. If aⁱ = k for some k then the palm tree is called regular, and it is denoted by Sn(k) := Sn(k, k, . . . , k). Other graph theory related definitions can be found in [7].

2. Partition dimension of trees

In this section, we emphasize the importance of studying the partition dimension of palms by giving a construction of a resolving partition of trees using resolving partitions of their palms. This construction provides an upper bound for the partition dimension of trees using the partition dimensions of their palms.

Theorem 2.1. Let T be a tree with b end-palms, P1, P2, . . . , Pb, then

\[pd(T) \le 1 - b + \sum_{i=1}^{b} pd(P_i).\]

Consider the following observation and lemma before proving Theorem 2.1.

Figure 1. Graph \(O_5 = S_5(1, 2, 3, 4, 5)\)

Observation 2.1. Let G be a graph and \(\Pi = \{S_1, \dots, S_n\}\) a resolving partition of G, then

• 1. Permuting the order of \(S_i\)'s (the indices) preserves the resolving property.
• 2. For every vertex v of G and index \(i \in \{1, 2, ..., n\}\), there is a resolving partition where v is in the i^th partition.

Lemma 2.1 ([3]). Let G be a graph and xy a bridge of G. Let \(G_x\) and \(G_y\) be the component of G-xy containing x and y respectively. Let \(\Pi=\{S_1,\ldots,S_n\}\) be a partition of V(G). If \(S_i\subseteq V(G_x)\) and \(S_j\subseteq V(G_y)\) for some \(S_i\) and \(S_j\) in \(\Pi\), then the representation of any vertex \(u\in V(G_x)\) and \(v\in V(G_y)\) is different.

Proof of Theorem 2.1. If b=1, then T is a palm and the result follows. Let \(b \geq 2\), \(l_0=2\), and \(l_i=2+\sum_{k=1}^i(pd(P_i)-1)\) for other i. Consider the following partition construction.

• 1. For every palm \(P_i\) in T, let \(\Pi_i = \{S_1, S_{l_{i-1}}, S_{l_{i-1}+1}, \dots, S_{l_{i-1}}\}\) be a resolving partition of \(P_i\) with the hub vertex in \(S_1\). This is possible because of Observation 2.1.
• 2. Put every other vertex (the one not in an end-path) in \(S_1\).

Note that the partition construction above uses \(l_b - 1 = 1 - b + \sum pd(P_i)\) partitions and every palm \(P_i\) contains a unique partition \(S_{l_{i-1}}\). This partition is a resolving partition because two vertices in the same palm are resolved by the existing resolving partition in that palm, and two vertices not in the same palm have different representations by Lemma 2.1.

3. Partition dimension of palm

Now that we know the importance of the partition dimension of palms, we can focus this section on studying the partition dimension of palms. The relation between the partition dimension of a palm and its maximum degree is given in the following theorem.

Theorem 3.1. [5] If G is a graph with \(pd(G) = k \ge 3\), then \(\Delta(G) \le 3^{k-1} - 1\).

We will use the previous theorem to find the bounds for the partition dimension of palms.

Theorem 3.2. Let n ≥ 2 and G = Sn(a1, a2, . . . , an) be a palm, then

\[\lfloor \log_3 n \rfloor + 2 \le pd(G) \le n.\]

Proof. The lower bound is a direct consequence of Theorem 3.1. The upper bound is achieved by putting each end-path in a different partition, the hub vertex can be included in any partition.

This bound is useful for characterizing infinite trees with finite dimensions, see [4] and [9].

It's not hard to see that the upper bound in Theorem 3.2 is only satisfied by the star graph. However, the lower ground is achieved by many palms, consider the following family of palms. A palm Sn(a1, a2, . . . , an) is said to have property A if a^{3 k}+1 ≥ 2k + 1 and a2·^{3 k}+1 ≥ 2k + 2 for all non negative integers k < log³ n. For example if ∆(G) = 27, then the requirements for property A is a³ ≥ 2, a⁴ ≥ 3, a⁷ ≥ 4, a¹⁰ ≥ 5, and a¹⁹ ≥ 6. Remember that {ai} is non decreasing so this means G has at least different end-paths with 1 end-path of length at least 2, 3 end-paths of length at least 3, 3 end-paths of length at least 4, 9 end-paths of length at least 5, and 9 end-paths of length at least 6.

Theorem 3.3. Let G = Sn(a1, a2, . . . , an) be a palm with property A, then pd(G) = ⌊log³ n⌋ + 2.

Proof. If n = 2, G is a path and the result follows, so let n ≥ 3 be an integer. Note that that pd(G) = ⌊log³ n⌋ + 2 is equivalent to

\[pd(G) = k \iff 3^{k-2} \le n \le 3^{k-1} - 1.\] (1)

By Theorem 3.2, pd(G) ≥ ⌊log³ n⌋ + 2. Now we give an algorithm to make a partition Π = {S1, . . . , Sk} of with k = ⌊log³ n⌋ + 2.

• 1. For i = 1, . . . , n; write i = 1 + (i − 1)³ where (i − 1)³ is written as a (k − 1)-digit numbers in base 3, allowing the first digit to be zero, this is always possible by (1). For example if n = 26, then k = 4 and write 20 = 1 + (201)³ and 9 = 1 + (022)3.
• 2. Define n distinct integer-sequences A^l = {a l 1 , a^l 2 , a^l 3 , . . .}, 0 ≤ l ≤ n − 1, with the following algorithm.
  • Initially, define each A^l as the sequence of all 1s, i.e., A^l = {1, 1, 1, 1, 1, 1, 1, 1, . . .}.
  • Write l = 1 + (lklk−¹ · · · l3l2)³ as in step 1.
  • For t = 2, . . . , k, if l^t ̸= 0, reassign the value of a l ^s with t for every s ≥ 2t − 4 + l^t

For example if n = 26, then k = 4 and the sequences A^l for l = 1, 15, 20 and 25 are as follows:

\[A_1 = A_{1+(000)_3} = \{1, 1, 1, 1, 1, 1, 1, \dots\}\] \[A_{15} = A_{1+(112)_3} = \{1, 2, 3, 3, 4, 4, 4, \dots\}\] \[A_{20} = A_{1+(201)_3} = \{2, 2, 2, 2, 2, 4, 4, \dots\}\] \[A_{25} = A_{1+(220)_3} = \{1, 1, 1, 3, 3, 4, 4, \dots\}\]

3. Assign ai,j ∈ S^a i j . Also assign a⁰ ∈ S^k if n = 3^k−² and a⁰ ∈ S¹ otherwise.

.

Now we prove that the representations of all vertices are different. Note that the sequence \(A_l\) has the following properties: (a) \(A_l\) is an increasing sequence, (b) \(A_l\) is different for every l, (c) \(a_1^l \in \{1,2\}\) for every l, (d) If \(A_l\) contains a term with value t (\(l_t \neq 0\)), then the first term with value t is \(a_{2t-3}^l\) (if \(l_t=1\)) or \(a_{2t-2}^l\) (if \(l_t=2\)), and (e) If \(n>3^{k-2}\), then for every \(t\in \{2,\ldots,k\}\) there exists an l such that \(a_{2t-3}^l=t\).

(A) First, consider if \(3^{k-2}+1 \le n \le 3^{k-1}-1\). The representation of the hub is \(r(a_{0,0}|\Pi)=(0,1,3,5,\ldots,2k-3)\) by the above properties (d) and (e). Suppose there is another vertex with the same representation, say \(r(a_{i,j})=r(a_{0,0})\) with \((i,j)\ne (0,0)\). We will prove that \(A_i\) contains every value \(t, 1 \le t \le k\). Suppose otherwise, \(A_i\) does not contains any term of value t for some t, then the shortest path from \(a_{i,j}\) to a vertex in \(S_t\) contains the hub vertex, which means \(d(a_{i,j},S_t)>d(a_{0,0},S_t)\).

Now, for every \(t, 2 \le t \le k\), let \(a^i_{s_t}\) be the first term in \(A_i\) which is equal to t. From the property (d), we have \(s_t \le 2t-2\) and since \(s_t-j=d(a_{i,j},a_{i,s_t})=d(a_{i,j},S_t)=d(v,S_t)=2t-2\), then j=0 and \(s_t=2t-2\) which means that \(i=1+(222\cdots 2)_3\). That implies \(i=3^{k-1}>n\), a contradiction.

Before we prove the representations of all vertices are different, note that if the \(i^{th}\) end-path contains a vertex in \(S_t\) then the nearest vertex in \(S_t\) from a vertex \(a_{i,j}\) is always a vertex in this end-path. If the \(i^{th}\) end-path does not contain a vertex in \(S_t\) then \(d(a_{i,j}, S_t) = 2t + j - 3\) by the properties (d) and (e).

Now we prove that \(r(a_{i,j}|\Pi) \neq r(a_{l,m}|\Pi)\) for \((i,j) \neq (l,m)\).

Case 1. j=m. Since \(i \neq l\) then \(A_i \neq A_l\) and \(a_s^i \neq a_s^l\) for some s. If s < j=m, \(S_z\) with \(z=\min\{a_s^i,a_s^l\}\) is going to distinguish \(r(a_{i,j}|\Pi)\) and \(r(a_{l,m}|\Pi)\) because \(A_i\) and \(A_l\) are monotone. If s>j=m, \(S_z\) with z is the largest between the value of \(a_s^i\) and \(a_s^l\) is going to distinguish \(r(a_{i,j}|\Pi)\) and \(r(a_{l,m}|\Pi)\) because \(A_i\) and \(A_l\) is monotone.

Case 2. \(j \neq m\). For a contradiction, suppose \(r(a_{i,j}|\Pi) = r(a_{l,m}|\Pi)\). Without loss of generality, assume j < m. First note that \(i \neq 0\), because if i = 0 then \(l \neq 1\) which means that there exists a term in \(A_l\) which is not 1 (say \(a_s^l = t > 1\)). This means that \(d(a_{0,1}, S_t) = 2t - 2 > 2t - 3 \ge d(a_{l,m}, S_t)\) by the properties (d) and (e). Next we prove m = j + 1.

If \(a_{i,j} \in S_1\) then \(a_{l,m} \in S_1\). We know that \(1 \leq j < m\), so \(m \geq 2\). This means that the second term of \(A_l\) is 1 and \(A_l\) does not contain a term with value 2, so \(d(a_{l,m}, S_2) = m + 1\). In any case whether \(A_i\) contains a term 2 or not, we obtain \(d(a_{i,j}, S_2) \leq j + 1\), which means that \(d(a_{l,m}, S_2) > d(a_{i,j}, S_2)\). Therefore \(a_{i,j} \notin S_1\).

Let \(a_s^i=t\) be the first term in \(A_i\) which is not 1. Note that \(d(a_{i,j},S_1)=d(a_{i,j},a_{i,s-1})=j-s+1\), then \(d(a_{l,m},S_1)=j-s+1\) which means that \(a_{m-j+s-1}^l=1\). Now \(m-j+s-1\geq s\), therefore \(a_s^l=a_{m-j+s-1}^l=1\). Since \(r(a_{i,j}|\Pi)=r(a_{l,m}|\Pi)\) and j>m, then \(A_l\) also contains a term which equals to t. Since \(a_s^i=t\) is the first term in \(A_i\) which is equal to t, by the property (d), the only possible way is for the first term of \(A_l\) which is equal to t must be \(a_{s+1}^l\) and m-j+s-1=s which means that m=j+1.

Now we prove that \(A_i\) and \(A_l\) both contain all the numbers \(t, 2 \le t \le k\). Suppose otherwise, there exists some \(t \in \{2,3,\ldots,k\}\) not in either \(A_i\) or \(A_l\) or both. If t is not contained in both of them, then \(d(a_{l,m},S_t)=2t+m-3>2t+j-3=d(a_{i,j},S_t)\) because m>j. If t is not contained in \(A_i\) but contained in \(A_l\), then \(d(a_{l,m},S_t)=|m-(2t-3)|=\max\{m,2t-3\}-\min\{m,2t-3\}\le m+2t-3-1=j+2t-3=d(a_{i,j},S_t)\) because m=j+1 and \(t\ge 2\). If t is not contained in

\(A_l\) but contained in \(A_i\), then \(d(a_{l,m}, S_t) = m + 2t - 3 > j \ge d(a_{i,j}, S_t)\) because m > j and \(t \ge 2\). Since m = j + 1, \(r(a_{i,j}|\Pi) = r(a_{l,m}|\Pi)\), and both \(A_i\) and \(A_l\) contain all \(t, 1 \le t \le k\), and also the properties (d) and (e), the first term in \(A_i\) which equal to \(t \ge 2\) must be \(a_{2t-3}^i\) and first term in \(A_l\) which equal to \(t \ge 2\) must be \(a_{2t-2}^l\). This implies that \(i = 1 + (111 \cdots 1)_3\) and \(l = 1 + (222 \cdots 2)_3\) and \(l = 3^{k-1} - 1 \ge n > l\), a contradiction. Therefore, the representations of all vertices are different.

(B) Now consider if \(n=3^{k-2}\). For every integer \(i\in[0,3^{k-2})\), the representation of i as a (k-1)-digit number in base 3 will always have the first digit to be zero. This means that k is not contained in any sequence \(A_l\) and \(S_k=\{v\}\). If \(r(a_{i,j}|\Pi)=r(a_{l,m}|\Pi)\) then their distances to \(S_k\) must be the same, which means they are at the same level. A similar argument as in Case II can be used to show that \(r(a_{i,j}|\Pi)\neq r(a_{l,m}|\Pi)\).

To conclude, we have constructed a resolving partition of G with \(k = \lfloor \log_3 n \rfloor + 2\) colors, and so \(pd(G) = \lfloor \log_3 n \rfloor + 2\).

Theorem 3.2 can be expressed in the following way:

Corollary 3.1. Let G be an \[\mathbb{A}\] palm. For \(k \geq 2\), \(pd(G) = k\) if and only if \(3^{k-2} \leq \Delta(G) \leq 3^{k-1} - 1\).

Since the lower bound and upper bound in Theorem 3.2 is achieved, by adapting the method in the proof of Theorem 4.1(2) in [10], for every k between \(\lfloor \log_3 n \rfloor + 2\) and n, there is an olive G with \(\Delta(G) = n\) and pd(G) = k.

One particular palm with property \(\mathbb{A}\) is the olive tree.

Corollary 3.2. For \[n \geq 2\], \(pd(O_n) = \lfloor \log_3 n \rfloor + 2\).

Note that for k=3 and k=4 Corollary 3.2 corrects the results stated in Theorem 7 and 8 in [2]. The corrected results are (1) \(pd(O_n)=3\) if and only if \(3 \le n \le 8\) and (2) \(pd(O_n)=4\) if and only if \(9 \le n \le 26\). Figure 3 shows a resolving partition of olive \(O_8\).

Figure 2. A resolving partition of \(O_8\).

The complexity of the locating chromatic number for regular palms is given in [10].

Theorem 3.4. [10] for every positive integer \[k\], \(\chi_L(S_n(k)) = \Theta\left(n^{\frac{1}{k}}\right)\).

The coloring algorithm in the proof of this theorem can be adapted for partition dimensions by setting the color classes as partitions. This means we have the following theorem.

Theorem 3.5. For every fixed positive integer \[k\], \(pd(S_n(k)) = \Theta\left(n^{\frac{1}{k}}\right)\).

We end this paper by giving a conjecture for a stronger value for the partition dimension of regular palms.

Conjecture 1. For \[k \ge 2\], \(pd(S_n(k)) = (1 + o(1)) (\frac{k-1}{2}) \sqrt[k]{4n}\).

Acknowledgement

This research has been supported by the PPMI research program, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Indonesia.

References

• [1] Amrullah, The partition dimension for a subdivision of a homogeneous firecracker, Electron. J. Graph Theory Appl. 8 (2) (2020), 445–455.
• [2] K.I.B.K.P. Arimbawa and E.T. Baskoro, Partition dimension of some classes of trees, Procedia Computer Science, 74 (2015), 67–72
• [3] E.T. Baskoro and D.I.D. Primaskun, Improved algorithm for the locating-chromatic number of trees, Theoretical Computer Science, 856 (2021), 165–168.
• [4] J. Caceres, C. Hernando, M. Nora, I.M. Pelayo, and M.L. Puertas, On the metric dimensions of infinite ´ graphs, Electron. Notes Discrete Math., 35 (2009), 15–20.
• [5] G.G. Chappell, J. Gimbel, and C. Hartman, Bounds on the metric and partition dimensions of a graph, Ars Comb., 88 (2008).
• [6] G. Chartrand, E. Salehi, and P. Zhang, The partition dimension of a graph, Aequationes Mathematicae, 59 (2000), 45–54.
• [7] R. Diestel, Graph Theory, Fifth Edition, Springer, 2017.
• [8] K.Q. Fredlina and E.T. Baskoro, The partition dimension of some families of trees, Procedia Computer Science, 74 (2015) 60–66
• [9] Y. Hafidh and E.T. Baskoro, Infinite trees with finite dimensions, DOI: 10.5220/0009876300002775, Proceedings of the 1st International MIPAnet Conference on Science and Mathematics (IMC-SciMath 2019), pages 11–13, Scitepress, ISBN: 978-989-758-556-2.
• [10] Y. Hafidh and E.T. Baskoro, On the locating chromatic number of trees, Int. J. Math. Comput. Sci., 17 (2022), 377–394.
• [11] D.O. Haryeni, E.T. Baskoro, and S.W. Saputro, A method to construct graphs with certain partition dimension, Electron. J. Graph Theory Appl. 7 (2) (2019), 251–263.

• [12] J.A. Rodrigues-Velazquez, I.G. Yero, and M. Lema ´ nska, On the partition dimension of trees, ´ Discrete Applied Mathematics, 166 (2014), 204–209.
• [13] P.J. Slater, Leaves of Trees, Proc. 6th S-E Conf. Combinatorics, Graph Theory and Computing, (1975), 549–559.