Electronic Journal of Graph Theory and Applications 12 .
, 265Ae272 Partition dimension of trees - palm approach Yusuf Hafidha .
Edy Tri Baskoroa,b Combinatorial Mathematics Research Group.
Faculty of Mathematics and Natural Sciences.
Institut Teknologi Bandung.
Indonesia b Center for Research Collaboration on Graph Theory and Combinatorics.
Indonesia emails: yusuf.
hafidh@itb.
id, ebaskoro@itb.
Abstract 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.
this paper, we construct a resolving partition for trees using resolving partitions of their palms.
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.
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 Si OO 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 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.
Partition dimension of trees - palm approach Hafidh and E.
Baskoro is given by r.
) = .
S1 ), d.
S2 ), .
, d.
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 .
, 12, .
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 .
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 .
Other different constructions were also proposed for computing partition dimensions of graphs, see .
A star Sn is the complete bipartite graph K1,n .
A palm Sn .
1 , a2 , .
, an ) for n Ou 2, is a graph obtained from a star Sn by subdividing the ith edge ai Oe 1 times.
Since permuting ai will result in an isomorphic graph, we always consider .
i } in a non-decreasing sequence.
Let us denote the vertex and edge set of a palm by V = .
0 } O .
i,j | 1 O i O n, 1 O j O ai }, and E = .
0 ai,1 | 1 O i O .
O .
i,j ai,j 1 | 1 O i O n, 1 O j O ai Oe .
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 .
0 } O .
k,j : 1 O j O ak }.
A palm is called an end-palm if it is the union of all end-paths from a branch.
If ai = i for every i then this palm tree is called an olive tree and denoted by On , namely On = Sn .
, 2, .
, .
Olive trees with partition dimensions 3 and 4 were studied in .
Figure 1 is an example of an olive tree O5 .
If ai = k for some k then the palm tree is called regular, and it is denoted by Sn .
:= Sn .
, k, .
, .
Other graph theory related definitions can be found in .
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.
Let T be a tree with b end-palms.
P1 .
P2 , .
Pb , then pd(T ) O 1 Oe b pd(Pi ).
Consider the following observation and lemma before proving Theorem 2.
Partition dimension of trees - palm approach Hafidh and E.
Baskoro Figure 1.
Graph O5 = S5 .
, 2, 3, 4, .
Observation 2.
Let G be a graph and = {S1 , .
Sn } a resolving partition of G, then Permuting the order of Si Aos .
he indice.
preserves the resolving property.
For every vertex v of G and index i OO .
, 2, .
, .
, there is a resolving partition where v is in the ith partition.
Lemma 2.
1 (.
Let G be a graph and xy a bridge of G.
Let Gx and Gy be the component of G Oe xy containing x and y respectively.
Let = {S1 , .
Sn } be a partition of V (G).
Si OI V (Gx ) and Sj OI V (Gy ) for some Si and Sj in , then the representation of any vertex u OO V (Gx ) and v OO V (Gy ) is different.
Proof of Theorem If b = 1, then T is a palm and the result follows.
Let b Ou 2, l0 = 2, and li = 2 ik=1 .
d(Pi ) Oe .
for other i.
Consider the following partition construction.
For every palm Pi in T , let i = {S1 .
SliOe1 .
SliOe1 1 , .
Sli Oe1 } be a resolving partition of Pi with the hub vertex in S1 .
This is possible because of Observation 2.
Put every other vertex .
he one not in an end-pat.
in S1 .
Note that the partition construction above uses lb Oe 1 = 1 Oe b pd(Pi ) partitions and every palm Pi contains a unique partition SliOe1 .
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.
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.
If G is a graph with pd(G) = k Ou 3, then OI(G) O 3kOe1 Oe 1.
We will use the previous theorem to find the bounds for the partition dimension of palms.
Partition dimension of trees - palm approach Hafidh and E.
Baskoro Theorem 3.
Let n Ou 2 and G = Sn .
1 , a2 , .
, an ) be a palm, then UOlog3 nUU 2 O pd(G) O n.
Proof.
The lower bound is a direct consequence of Theorem 3.
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 .
ItAos 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.
palm Sn .
1 , a2 , .
, an ) is said to have property A if a3k 1 Ou 2k 1 and a2A3k 1 Ou 2k 2 for all non negative integers k < log3 n.
For example if OI(G) = 27, then the requirements for property A is a3 Ou 2, a4 Ou 3, a7 Ou 4, a10 Ou 5, and a19 Ou 6.
Remember that .
i } 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.
Let G = Sn .
1 , a2 , .
, an ) be a palm with property A, then pd(G) = UOlog3 nUU 2.
Proof.
If n = 2.
G is a path and the result follows, so let n Ou 3 be an integer.
Note that that pd(G) = UOlog3 nUU 2 is equivalent to pd(G) = k NaNe 3kOe2 O n O 3kOe1 Oe 1.
By Theorem 3.
2, pd(G) Ou UOlog3 nUU 2.
Now we give an algorithm to make a partition = {S1 , .
Sk } of with k = UOlog3 nUU 2.
For i = 1, .
, n.
write i = 1 .
Oe .
3 where .
Oe .
3 is written as a .
Oe .
-digit numbers in base 3, allowing the first digit to be zero, this is always possible by .
For example if n = 26, then k = 4 and write 20 = 1 .
3 and 9 = 1 .
Define n distinct integer-sequences Al = .
l1 , al2 , al3 , .
}, 0 O l O n Oe 1, with the following A Initially, define each Al as the sequence of all 1s, i.
Al = .
, 1, 1, 1, 1, 1, 1, 1, .
A Write l = 1 .
k lkOe1 A A A l3 l2 )3 as in step 1.
A For t = 2, .
, k, if lt = 0, reassign the value of als with t for every s Ou 2t Oe 4 lt .
For example if n = 26, then k = 4 and the sequences Al for l = 1, 15, 20 and 25 are as A1 = A1 .
3 = .
, 1, 1, 1, 1, 1, 1, .
A20 = A1 .
3 = .
, 2, 2, 2, 2, 4, 4, .
A15 = A1 .
3 = .
, 2, 3, 3, 4, 4, 4, .
A25 = A1 .
3 = .
, 1, 1, 3, 3, 4, 4, .
Assign ai,j OO Saij .
Also assign a0 OO Sk if n = 3kOe2 and a0 OO S1 otherwise.
Partition dimension of trees - palm approach Hafidh and E.
Baskoro Now we prove that the representations of all vertices are different.
Note that the sequence Al has the following properties: .
Al is an increasing sequence, .
Al is different for every l, .
al1 OO .
, .
for every l, .
If Al contains a term with value t .
t = .
, then the first term with value t is al2tOe3 .
f lt = .
or al2tOe2 .
f lt = .
, and .
If n > 3kOe2 , then for every t OO .
, .
, .
there exists an l such that al2tOe3 = t.
(A) First, consider if 3kOe2 1 O n O 3kOe1 Oe 1.
The representation of the hub is r.
0,0 |) = .
, 1, 3, 5, .
, 2k Oe .
by the above properties .
Suppose there is another vertex with the same representation, say r.
i,j ) = r.
0,0 ) with .
, .
= .
, .
We will prove that Ai contains every value t, 1 O t O k.
Suppose otherwise.
Ai does not contains any term of value t for some t, then the shortest path from ai,j to a vertex in St contains the hub vertex, which means d.
i,j .
St ) > d.
0,0 .
St ).
Now, for every t, 2 O t O k, let aist be the first term in Ai which is equal to t.
From the property .
, we have st O 2t Oe 2 and since st Oe j = d.
i,j , ai,st ) = d.
i,j .
St ) = d.
St ) = 2t Oe 2, then j = 0 and st = 2t Oe 2 which means that i = 1 .
A A A .
That implies i = 3kOe1 > n, a Before we prove the representations of all vertices are different, note that if the ith end-path contains a vertex in St then the nearest vertex in St from a vertex ai,j is always a vertex in this end-path.
If the ith end-path does not contain a vertex in St then d.
i,j .
St ) = 2t j Oe 3 by the properties .
Now we prove that r.
i,j |) = r.
l,m |) for .
, .
= .
, .
Case 1.
j = m.
Since i = l then Ai = Al and ais = als for some s.
If s < j = m.
Sz with z = min.
is , als } is going to distinguish r.
i,j |) and r.
l,m |) because Ai and Al are monotone.
If s > j = m.
Sz with z is the largest between the value of ais and als is going to distinguish r.
i,j |) and r.
l,m |) because Ai and Al is monotone.
Case 2.
j = m.
For a contradiction, suppose r.
i,j |) = r.
l,m |).
Without loss of generality, assume j < m.
First note that i = 0, because if i = 0 then l = 1 which means that there exists a term in Al which is not 1 .
ay als = t > .
This means that d.
0,1 .
St ) = 2t Oe 2 > 2t Oe 3 Ou d.
l,m .
St ) by the properties .
Next we prove m = j 1.
If ai,j OO S1 then al,m OO S1 .
We know that 1 O j < m, so m Ou 2.
This means that the second term of Al is 1 and Al does not contain a term with value 2, so d.
l,m .
S2 ) = m 1.
any case whether Ai contains a term 2 or not, we obtain d.
i,j .
S2 ) O j 1, which means that d.
l,m .
S2 ) > d.
i,j .
S2 ).
Therefore ai,j OO / S1 .
Let as = t be the first term in Ai which is not 1.
Note that d.
i,j .
S1 ) = d.
i,j , ai,sOe1 ) = j Oe s 1, then d.
l,m .
S1 ) = j Oe s 1 which means that almOej sOe1 = 1.
Now m Oe j s Oe 1 Ou s, therefore als = almOej sOe1 = 1.
Since r.
i,j |) = r.
l,m |) and j > m, then Al also contains a term which equals to t.
Since ais = t is the first term in Ai which is equal to t, by the property .
, the only possible way is for the first term of Al which is equal to t must be als 1 and mOej sOe1 = s which means that m = j 1.
Now we prove that Ai and Al both contain all the numbers t, 2 O t O k.
Suppose otherwise, there exists some t OO .
, 3, .
, .
not in either Ai or Al or both.
If t is not contained in both of them, then d.
l,m .
St ) = 2t m Oe 3 > 2t j Oe 3 = d.
i,j .
St ) because m > j.
If t is not contained in Ai but contained in Al , then d.
l,m .
St ) = .
Oe.
tOe.
| = max.
, 2tOe.
Oemin.
, 2tOe.
O m 2t Oe 3 Oe 1 = j 2t Oe 3 = d.
i,j .
St ) because m = j 1 and t Ou 2.
If t is not contained in Partition dimension of trees - palm approach Hafidh and E.
Baskoro Al but contained in Ai , then d.
l,m .
St ) = m 2t Oe 3 > j Ou d.
i,j .
St ) because m > j and t Ou 2.
Since m = j 1, r.
i,j |) = r.
l,m |), and both Ai and Al contain all t, 1 O t O k, and also the properties .
, the first term in Ai which equal to t Ou 2 must be ai2tOe3 and first term in Al which equal to t Ou 2 must be al2tOe2 .
This implies that i = 1 .
A A A .
3 and l = 1 .
A A A .
3 and l = 3kOe1 Oe 1 Ou n > l, a contradiction.
Therefore, the representations of all vertices are (B) Now consider if n = 3kOe2 .
For every integer i OO .
, 3kOe2 ), the representation of i as a .
Oe .
-digit number in base 3 will always have the first digit to be zero.
This means that k is not contained in any sequence Al and Sk = .
If r.
i,j |) = r.
l,m |) then their distances to Sk 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.
i,j |) = r.
l,m |).
To conclude, we have constructed a resolving partition of G with k = UOlog3 nUU 2 colors, and so pd(G) = UOlog3 nUU 2.
Theorem 3.
2 can be expressed in the following way:
Corollary 3.
Let G be an A palm.
For k Ou 2, pd(G) = k if and only if 3kOe2 O OI(G) O 3kOe1 Oe1.
Since the lower bound and upper bound in Theorem 3.
2 is achieved, by adapting the method in the proof of Theorem 4.
, for every k between UOlog3 nUU 2 and n, there is an olive G with OI(G) = n and pd(G) = k.
One particular palm with property A is the olive tree.
Corollary 3.
For n Ou 2, pd(On ) = UOlog3 nUU 2.
Note that for k = 3 and k = 4 Corollary 3.
2 corrects the results stated in Theorem 7 and 8 in .
The corrected results are .
pd(On ) = 3 if and only if 3 O n O 8 and .
pd(On ) = 4 if and only if 9 O n O 26.
Figure 3 shows a resolving partition of olive O8 .
Figure 2.
A resolving partition of O8 .
The complexity of the locating chromatic number for regular palms is given in .
Partition dimension of trees - palm approach Hafidh and E.
Baskoro Theorem 3.
for every positive integer k.
NL (Sn .
) = o n 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.
For every fixed positive integer k, pd(Sn .
) = o n k .
We end this paper by giving a conjecture for a stronger value for the partition dimension of regular palms.
Oo Conjecture 1.
For k Ou 2, pd(Sn .
) = .
) kOe1 Acknowledgement This research has been supported by the PPMI research program.
Faculty of Mathematics and Natural Sciences.
Institut Teknologi Bandung.
Indonesia.
References