# The Multibases of Symmetric Caterpillars

Authors: Supachoke Isariyapalakul; Varanoot Khemmani; Witsarut Pho-on
Journal: Journal of Mathematics
 (2020)

---

## Abstract

For a setW=w1,w2,…,wk of vertices and a vertex v of a connected graph G, the k-multiset mrvW=dv,w1,dv,w2,…,dv,wk, where dv,wi is the distance from v to wi for i=1,2,…,k, and is the multirepresentation of v with respect to W. The set W is a multiresolving set of G if the multirepresentations of every two distinct vertices of G with respect to W are distinct. The multiresolving set of G having the minimum cardinality is called a multibasis of G. The cardinality of a multibasis of G is the multidimensiondimMG of G. A caterpillar cak1,k2,…,ks is called a symmetric caterpillar if ki=ks−i+1 for all integers i with 1≤i≤s. In this work, the multiresolving sets of symmetric caterpillars are studied.


---

## Body

## 1. Introduction

For an ordered setW=w1,w2,…,wk of vertices and a vertex v of a connected graph G, we refer to the following k-vector:(1)rvW=dv,w1,dv,w2,…,dv,wk,as the representation of v with respect to W, where du,wi is the distance between v and wi for 1≤i≤k. The ordered set W is a resolving set of G if any two distinct vertices have distinct representations with respect to W. A resolving set of G containing a minimum number of vertices is a minimum resolving set or a basis of G. The dimension of G is the number of vertices in a basis of G and denoted by dimG. To illustrate these concepts, consider a connected graph G of Figure 1 with a vertex set VG=u,v,w,x,y,z.Figure 1
A connected graphG.For an ordered setW=u,w based of Figure 1, the representations of vertices of G with respect to W are(2)ruW=0,3,rvW=1,2,rwW=3,0,rxW=2,1,ryW=3,2,rzW=4,3.Since the representations of two distinct vertices with respect toW are distinct, it follows that W is a resolving set of G. Using a case-by-case analysis, we can show that G contains no 1-element resolving set and so W is a basis of G. Then, dimG=2.Resolving sets have previously appeared in [1]. In [2], and later in [3], Slater introduced these ideas and used a locating set for what we have called a resolving set. He referred to the cardinality of a basis in a graph G as its location numberlocG. Hulme, Shiver, and Slater described in [4–6] the usefulness of these ideas when working with US sonar and coast guard Loran (long-range aids to navigation) stations. Harary and Melter [7] discovered the concept of location number independently as well but used the term of dimension. Recently, these concepts were rediscovered by Johnson [8] of the Pharmacia Company while attempting to develop a capability of large datasets of chemical graphs. More applications of these concepts to navigation of robots in networks and other areas are discussed in [9].In general, a representation of a vertex with respect to an ordered setW in a connected graph G is a vector. We then consider a set W of vertices of G for which every vertex of G has a representation with respect to W in terms of a multiset.For a setW=w1,w2,…,wk of vertices and a vertex v of a connected graph G, the multirepresentationof v with respect to W is a k-multiset:(3)mrvW=dv,w1,dv,w2,…,dv,wk.To emphasize that this is a multirepresentation ofv with respect to W in G, we sometimes denote this multirepresentation by mrGvW. The set W is called a multiresolving set of G if every two distinct vertices have distinct multirepresentations with respect to W. A multiresolving set of G containing a minimum cardinality is called a minimum multiresolving set or a multibasis of G and this cardinality is the multidimension of G, which is denoted by dimMG.To illustrate these concepts, consider a connected graphG of Figure 1. We now know that the set W=u,w is a resolving set of G. However, since mruW=0,3=mrwW, it follows that W is not a multiresolving set of G. On the other hand, the set W′=u,v,z is a multiresolving set of G since the multirepresentations of vertices of G with respect to W′ are(4)mruW′=0,1,4,mrvW′=0,1,3,mrwW′=2,3,3,mrxW′=1,2,2,mryW′=1,2,3,mrzW′=0,3,4.SinceG contains neither 1-element nor 2-element multiresolving set of G, it follows that W′ is a multibasis of G; that is, dimMG=3.Forn≥3, the complete graph Kn contains no multiresolving set; that is, dimMKn is not defined which is described in [10]. In fact, dimMG is not defined for all connected graphs G. However, for a connected graph G of order n such that dimMG is defined, every multiresolving set of G is also a resolving set of G, and so,(5)1≤dimG≤dimMG≤n.For a setW of vertices of a connected graph G, the multirepresentation of vertices of W with respect to W contains 0. On the other hand, the vertices of G whose multirepresentations with respect to W do not contain 0 are vertices in VG−W. Therefore, to determine whether a set W is a multiresolving set of G, it suffices to show that every two distinct vertices in W have distinct multirepresentations with respect to W and then determine that multirepresentations with respect to W of all vertices in VG−W are distinct.The concepts of multiresolving set and multidimension were introduced in [10] and further studied in [11–13].


## 2. Preliminaries

For two verticesu and v of a connected graph G, if du,x=dv,x for all x∈VG−u,v, then u and v are distance-similar. Distance similarity is an equivalence relation on VG. For example, consider the cycle C4=v1,v2,v3,v4. There are two distance-similar equivalence classes, one that is v1,v3 and one that is v2,v4. The distance-similar equivalence class is useful to verify the multiresolving set of a connected graph as the following results.Theorem 1 (see [10]).
LetG be a connected graph such that dimMG is defined. If U is a distance-similar equivalence class in G with U=2, then every multiresolving set of G contains exactly one vertex of U.Theorem 2 (see [10]).
IfU is a distance-similar equivalence class in a connected graph G with U≥3, then dimMG is not defined.It was shown in [10, 13] that a path Pn=u1,u2,…,un is the only connected graph with multidimension 1 and u1 and un are the only two multibases of Pn for n≥2. There is no connected graph with multidimension 2. We state these results in the next theorems.Theorem 3 (see [10, 13]).
LetG be a connected graph. Then, dimMG=1 if and only if G=Pn, the path of order n.Theorem 4 (see [10, 13]).
A connected graph has no multiresolving set of cardinality 2.The following useful results for finding a multiresolving set of a connected graph were described in [12].Theorem 5 (see [12]).
LetG be a connected graph such that dimMG is defined, and let W be a multiresolving set of G. If v is an end-vertex of G such that v∉W, then W is a multiresolving set of G−v.Theorem 6 (see [12]).
LetG be a connected graph such that dimMG is defined, and let W be a multiresolving set of G. If v1,v2,…,vt are end-vertices of G such that v1,v2,…,vt∉W, then W is a multiresolving set of G−v1,v2,…,vt.Theorem 7 (see [12]).
LetT be a tree of order at least 3 containing a vertex u. If W is a multiresolving set of T, then W contains at least one vertex from each of degTu components of T−u, with one possible exception.


## 3. Multibases of Symmetric Caterpillars

A caterpillar is a tree of order at least 3 in which the removal of all end-vertices results in a path. This path is called thespine of a caterpillar. A vertex of the spine of a caterpillar is called a spine-vertex. Let T be a caterpillar such that dimMT is defined. Since any two end-vertices that are adjacent to the same spine-vertex of T are distance-similar, it follows from Theorem 2 that there are at most two end-vertices being adjacent to each spine-vertex of T. Therefore, we consider multibases of such a caterpillar T. In order to do this, some additional definitions and notation are introduced. For integers s,k1,k2,…,ks with s≥1, 1≤k1,ks≤2, and 0≤k2,k3,…,ks−1≤2, let cak1,k2,…,ks be a caterpillar which is obtained from the spine u1,u2,…,us by joining ki end-vertices to the spine-vertex ui, where 1≤i≤s. Observe that if ki=0, then there is no end-vertex joining to the spine-vertex ui. Also, if ki=1, then the spine-vertex ui is adjacent to an end-vertex which is called the first end-vertexvi of ui. Furthermore, if ki=2, then there are two end-vertices joining to ui that are called the first and second end-vertices of ui and denoted by vi and wi, respectively. For each integer i with 1≤i≤s, we define the set Ψ=i∈ℤki=2 to be the second end-set of a caterpillar cak1,k2,…,ks. To emphasize that this is the second end-set Ψ of a caterpillar T, we sometimes denote this set by ΨT. The caterpillar ca1,2,0,2,1,2,2 with the second end-set Ψ=2,4,6,7 is illustrated in Figure 2.Figure 2
The caterpillarca1,2,0,2,1,2,2 with Ψ=2,4,6,7.The caterpillars having multidimension 3 were studied and characterized in [12]. This suggests a way of investigating caterpillars having the multidimension of at least 3. Notice that the multidimension of a caterpillar is established by its second end-set Ψ. For a caterpillar cak1,k2,…,ks, observe that for each i∈Ψ, if s−i+1∈Ψ, then the multirepresentations of second end-vertices wi and ws−i+1 with respect to the set W=wii∈Ψ are the same. This leads us to determine a multibasis of a particular caterpillar. In order to do this, we need an additional definition. A caterpillar cak1,k2,…,ks is called a symmetric caterpillar if ki=ks−i+1 for each integer i with 1≤i≤s. For instance, the symmetric caterpillar ca2,0,2,1,2,0,2 is shown in Figure 3.Figure 3
The symmetric caterpillarca2,0,2,1,2,0,2Fors=1, the symmetric caterpillar ca2 is a path. Theorem 3 implies that its multidimension is 1 with multibases v1 and w1. For s=2, there are two symmetric caterpillars ca1,1 and ca2,2. Indeed, ca1,1 is a path whose multidimension is 1 with a multibasis v1. It is routine to verify that the multidimension of ca2,2 is 3 with a multibasis u1,w1,w2. Multibases of these caterpillars are indicated in Figure 4 by solid vertices.Figure 4
The symmetric caterpillarca2, ca1,1, and ca2,2As mentioned earlier, the multidimension of a path is 1. We may therefore consider symmetric caterpillars that are not a path. Fors≥3, let T be a symmetric caterpillar cak1,k2,…,ks that is not a path. If Ψ=0, then T is a symmetric caterpillar cak1,k2,…,ks with kr=1 for some r∈2,3,…,s−1. It is shown in [12] that a set u1,v1,vs is a multibasis of T, and so dimMT=3. If Ψ=1, then there is only one integer i belonging to Ψ for some i∈1,2,…,s. Since T is a symmetric caterpillar, it follows that i=s−i+1, and so i=s+1/2. This implies that s is odd and Ψ=s+1/2. Thus, there are two possibilities: (1) s=3 or (2) s>3. For s=3, the symmetric caterpillar T≅ca1,2,1 has multidimension 4 with a multibasis u1,v1,v3,w2. For s>3, a symmetric caterpillar T has multidimension 3 with a multibasis u1,vs,ws+1/2. We therefore investigate a multibasis and the multidimension of a symmetric caterpillar cak1,k2,…,ks with Ψ≥2, where s≥3. The following useful results are shown in [12], as we state next.Proposition 1 (see [12]).
Lets,α,andβ be integers with s≥3 and 1≤α<β≤s, and let W be a set of vertices of a caterpillar cak1,k2,…,ks containing one of v1,w1 and one of vs,ws. If mruαW=mruβW or mrvαW=mrvβW, then 1≤α≤⌈s/2⌉ and β=s−α+1.Proposition 2 (see [12]).
Lets,γ,andδ be integers with s≥3 and 1≤γandδ≤s, and let W be a set of vertices of a caterpillar cak1,k2,…,ks containing one of v1,w1 and one of vs,ws. Then,(i)
If1≤γ<δ≤s and mrvγW=mruδW, then 1≤γ≤⌈s/2⌉ and δ=s−γ+2(ii)
If1≤δ≤γ≤s and mrvγW=mruδW, then ⌈s/2⌉+1≤γ≤s and δ=s−γProposition 3 (see [12]).
Lets,α,andβ be integers with s≥3 and 1≤α<β≤s, and let W be a set of vertices of a caterpillar cak1,k2,…,ks containing u1 and one of vs,ws except v1 and w1. If mruαW=mruβW or mrvαW=mrvβW, then 1≤α≤⌈s/2⌉ and β=s−α+2.Proposition 4 (see [12]).
Lets,γ,andδ be integers with s≥3 and 1≤γ,δ≤s, and let W be a set of vertices of a caterpillar cak1,k2,…,ks containing u1 and one of vs,ws except v1 and w1. Then,(i)
If1≤γ<δ≤s and mrvγW=mruδW, then 1≤γ≤⌈s/2⌉ and δ=s−γ+3(ii)
If1≤δ≤γ≤s and mrvγW=mruδW, then ⌈s/2⌉+1≤γ≤s and δ=s−γ+1
The following observation is a consequence of Theorem1.Observation 1.
Every multiresolving set of a caterpillarcak1,k2,…,ks with a second end-set Ψ contains either first end-vertex vi or second end-vertex wi, where i∈Ψ.
By Observation1, the multidimension of a symmetric caterpillar cak1,k2,…,ks with a second end-set Ψ must be at least Ψ. In fact, its multidimension is at least Ψ+1, as we now show.Proposition 5.
Fors≥3, let T be a symmetric caterpillar cak1,k2,…,ks such that dimMT is defined with the second end-set Ψ. Then, dimMT≥Ψ+1.Proof.
IfΨ=0, then the result holds. We may assume for Ψ≥1 that the statement of the proposition is false. Then, there is a symmetric caterpillar cak1,k2,…,ks having a multiresolving set W with W≤Ψ. By Observation 1, W=Ψ. However, then, mru1W=mrusW, contradicting W as being a multiresolving set of cak1,k2,…,ks.
Proposition5 states that Ψ+1 is a lower bound for the multidimension of a symmetric caterpillar. Furthermore, we also establish that Ψ+3 is an upper bound for the multidimension of a symmetric caterpillar, as follows.Proposition 6.
Fors≥3, let T be a symmetric caterpillar cak1,k2,…,ks such that dimMT is defined with a second end-set Ψ. Then, dimMT≤Ψ+3.Proof.
To showdimMT≤Ψ+3, it suffices to verify that there is a multiresolving set of T having cardinality at most Ψ+3. Let W be the set of all second end-vertices of T with W=Ψ. We consider three cases for Ψ.Case 1.
1 belongs toΨ.
We claim thatB=W∪u1 is a multiresolving set of T. Assume, contrary to our claim, that there are two vertices x and y of T such that mrxB=mryB. We consider two subcases.Subcase 1.1. Bothx and y belong to B.First, we show that bothx and y belong to W. Suppose, to the contrary, that either x or y does not belong to W, say x. Then, x=u1. Since u1 and w1 are the only two adjacent vertices of B, it follows that mru1B contains 1, and so y=w1. However, since du1,ws and dw1,ws are the maximum elements of mru1B and mrw1B, respectively, it follows that du1,ws=dw1,ws, which is a contradiction. Therefore, both x and y must belong to W. Next, we let x=wα and y=wβ, where 1≤α<β≤s. If 1≤α<β≤⌈s/2⌉, then dwα,ws=s−α+2 and dwβ,ws=s−β+2 are the maximum elements of mrwαB and mrwβB, respectively. Therefore, α=β, producing a contradiction. Similarly, if ⌈s/2⌉+1≤α<β≤s, then dwα,w1=α+1 and dwβ,w1=β+1 must be equal, that is, α=β, which is impossible. We may assume that 1≤α≤⌈s/2⌉ and ⌈s/2⌉+1≤β≤s. Since dwα,ws=s−α+2 and dwβ,w1=β+1 are the maximum elements of mrwαB and mrwβB, respectively, it follows that β=s−α+1. Since T is a symmetric caterpillar, it follows that mrwαW=mrwβW. However, since dwα,u1<dwβ,u1, it follows that mrwαB≠mrwβB, this contradicts our assumption.Subcase 1.2. Neitherx nor y belongs to B.We consider three subcases.Subcase 1.2.1.x and y are spine-vertices.Letx=uα and y=uβ, where 2≤α<β≤s. Applying Proposition 1, we obtain that 2≤α≤⌈s/2⌉ and β=s−α+1. Since mruαW=mrus−α+1W and duα,u1<dus−α+1,u1, it follows that mruαB≠mruβB, which is a contradiction.Subcase 1.2.2.x and y are first end-vertices.Letx=vα and y=vβ, where 1≤α<β≤s. By Proposition 1, 1≤α≤⌈s/2⌉ and β=s−α+1. Since mrvαW=mrvs−α+1W and dvα,u1<dvs−α+1,u1, it follows that mrvαB≠mrvβB, this is also a contradiction.Subcase 1.2.3.x is a first end-vertex and y is a spine-vertex.IfΨ=1,s, then it is shown in [12] that the set u1,w1,ws is a multiresolving set of T. We therefore consider the second end-set of cardinality at least 3. Let p=minΨ−1,s. By the symmetry of T, s−p+1=maxΨ−1,s. Let x=vγ and y=uδ, where 1≤γ,δ≤s. We consider two subcases for γ and δ.Subcase 1.2.3.1.1≤γ<δ≤s.By Proposition2 (i), 1≤γ≤⌈s/2⌉ and δ=s−γ+2. Since dvγ,ws and duδ,w1 are the maximum elements of mrvγB and mruδB, respectively, it follows that maxmrvγB−ws=dvγ,ws−p+1=s−p−γ+3 and maxmruδB−w1=duδ,u1=δ−1 are the same. Consequently, p=2 and so δ−1=s−γ+1. Since duδ,u1 and duδ,w2 are in mruδB, it follows that mrvγB also contains two s−γ+1s. Notice that us, vs−1, and ws−1 are the only three vertices of T whose distance from vγ is s−γ+1=δ−1. Since us and vs−1 do not belong to B, it follows that mrvγB contains only one element of s−γ+1, which contradicts our assumption.Subcase 1.2.3.2.2≤δ≤γ≤s.Applying Proposition2 (ii), we obtain that ⌈s/2⌉+1≤γ≤s and δ=s−γ. Since dvγ,w1 and duδ,ws are the maximum elements of mrvγB and mruδB, respectively, it follows that maxmrvγB−w1=dvγ,u1=γ and maxmruδB−ws=duδ,ws−p+1=s−p−δ+2 are the same. Certainly, p=2 and so γ=s−δ. Since dvγ,u1 and dvγ,w2 are in mrvγB, it follows that mruδB also contains two s−δs. Notice that us, vs−1, and ws−1 are the only three vertices of T whose distance from uδ is s−δ=γ. Since us and vs−1 do not belong to B, it follows that mruδB contains only one element of s−δ, which contradicts our assumption.
Hence, in Subcases 1.1 and 1.2 above,mrxB≠mryB for all x,y∈VT. This implies that B is a multiresolving set of T.Case 2.
1 and 2 do not belong toΨ.
Symmetrically,s−1 and s also do not belong to Ψ. Let p=minΨ. Then, s−p+1=maxΨ. We claim that B=W∪u1,vs is a multiresolving set of T. Suppose, contrary to our claim, that there are two vertices x and y such that mrxB=mryB. We consider two subcases.Subcase 2.1. Bothx and y belong to B.We first show thatu1,vs∉x,y. Assume, to the contrary, that u1=x. Since maxmru1B=du1,vs=maxmryB, it follows that y=vs. However, since du1,u1 and dvs,vs are the minimum elements of mru1B and mrvsB, respectively, and clearly, minmru1B−u1=du1,wp=p and minmrvsB−vs=dvs,ws−p+1=p−1, it follows that mru1B≠mrvsB, producing a contradiction. Thus, x and y belong to W. Next, we let x=wα and y=wβ, where p≤α<β≤s−p+1. If 1≤α<β≤⌈s/2⌉, then dwα,vs and dwβ,vs are the maximum elements of mrwαB and mrwβB, respectively. Therefore, α=β, which is a contradiction. Similarly, if ⌈s/2⌉+1≤α<β≤s, then dwα,u1 and dwβ,u1 must be equal, which is impossible. We may assume that 1≤α≤⌈s/2⌉ and ⌈s/2⌉+1≤β≤s. Since dwα,vs and dwβ,u1 are the maximum elements of mrwαB and mrwβB, respectively, it follows that β=s−α+2. Since maxmrwαB−vs=dwα,ws−p+1=s−p−α+3 and maxmrwβB−u1=dwβ,wp=β−p+2 are equal, it follows that, certainly, β=s−α+1, producing a contradiction.Subcase 2.2. Neitherx nor y belongs to B.We consider three subcases.Subcase 2.2.1.x and y are spine-vertices.Letx=uα and y=uβ, where 2≤α<β≤s. By applying Proposition 3, it implies that 2≤α≤⌈s/2⌉ and β=s−α+2. Since duα,vs and duβ,u1 are the maximum elements of mruαB and mruβB, respectively, it follows that maxmruαB−vs=duα,ws−p+1=s−p−α+2 and maxmruβB−u1=duβ,wp=β−p+1 must be equal. Necessarily, then, β=s−α+1. This is a contradiction.Subcase 2.2.2.x and y are first end-vertices.Letx=vα and y=vβ, where 1≤α<β≤s. By Proposition 3, 1≤α≤⌈s/2⌉ and β=s−α+2. Since dvα,vs and dvβ,u1 are the maximum elements of mrvαB and mrvβB, respectively, it follows that maxmrvαB−vs=dvα,ws−p+1=s−p−α+3 and maxmrvβB−u1=dvβ,wp=β−p+2 must be equal. Consequently, β=s−α+1. This is also a contradiction.Subcase 2.2.3.x is a first end-vertex and y is a spine-vertex.Letx=vγ and y=uδ, where 1≤γ,δ≤s. We consider two subcases according to γ and δ.Subcase 2.2.3.1.1≤γ<δ≤s.By Proposition4 (i), 1≤γ≤⌈s/2⌉ and δ=s−γ+3. Since dvγ,vs and duδ,u1 are the maximum elements of mrvγB and mruδB, respectively, it follows that maxmrvγB−vs=dvγ,ws−p+1=s−p−γ+3 and maxmruδB−u1=duδ,wp=p−δ+1 must be equal. Evidently, δ=s−γ+2, which is impossible.Subcase 2.2.3.2.2≤δ≤γ≤s.
Applying Proposition4 (ii), it implies that ⌈s/2⌉+1≤γ≤s and δ=s−γ+1. Since dvγ,u1 and duδ,vs are the maximum elements of mrvγB and mruδB, respectively, it follows that maxmrvγB−u1=dvγ,wp=γ−p+2 and maxmruδB−vs=duδ,ws−p+1=s−p−δ+2 are equal. As verified above, δ=s−γ, which cannot occur.
Hence,mrxB≠mryB for all x,y∈VT. This implies that B is a multiresolving set of T.Case 3.
1 does not belong toΨ and 2 belongs to Ψ.
LetT′ be a symmetric caterpillar which is obtained from T by joining end-vertices x and y to the spine-vertices u1 and us, respectively. Thus, 1∈ΨT′. By applying Case 1, B=W∪v1,vs∪u1 is a multiresolving set of T′. Since T≅T′−x,y, it follows by Theorem 6 that B=W∪u1,v1,vs is a multiresolving set of T.
Hence, every symmetric caterpillarT has a multiresolving set of cardinality of at most Ψ+3, and so dimMT≤Ψ+3.
The following result is obtained from the bounds given in Propositions5 and 6.Corollary 1.
Fors≥3, let T be a symmetric caterpillar cak1,k2,…,ks with the second end-set Ψ. Then,(6)Ψ+1≤dimMT≤Ψ+3.The multidimensions of symmetric caterpillars are characterized by the following result. Furthermore, the sharpnesses of Corollary1 are presented.Theorem 8.
Fors≥3, let T be a symmetric caterpillar cak1,k2,…,ks with Ψ≥2 and let W be a set of all second end-vertices. Then,(i)
If1∈Ψ, then W∪u1 is a multibasis of T(ii)
If1,2∉Ψ, then W∪u1,vs is a multibasis of T(iii)
If1∉Ψ and 2∈Ψ, then W∪u1,v1,vs is a multibasis of TProof.
(i)
Assume that1∈Ψ. By Case 1 in the proof of Proposition 6, it implies that W∪u1 is a multiresolving set of T. Hence, dimMT=Ψ+1 by Corollary 1, and so W∪u1 is a multibasis of T.(ii)
Assume that1,2∉Ψ. By Case 2 in the proof of Proposition 6, it implies that B=W∪u1,vs is a multiresolving set of T. Therefore, dimMT≤Ψ+2. Next, we claim that dimMT≥Ψ+2. Let p=minΨ. Since there are four components of T−up, it follows from Theorem 1 and Theorem 7 that at least one vertex from the component of T−up containing a vertex up−1, belongs to every multiresolving set of T. Similarly, every multiresolving set must contain at least one vertex from the component of T−us−p+1 containing us−p+2. Therefore, by Observation 1, every multiresolving set of T has cardinality at least Ψ+2. Hence, dimMT=Ψ+2 and so W∪u1,vs is a multibasis of T.(iii)
Assume that1∉Ψ and 2∈Ψ. By Case 3 in the proof of Proposition 6, it implies that W∪u1,v1,vs is a multiresolving set of T. Thus, dimMT≤Ψ+3. Next, we show that dimMT≥Ψ+3. Since there are four components of T−u2, it follows by Theorem 7 that every multiresolving set of T must contain at least one vertex of u1,v1. Similarly, every multiresolving set of T must contain at least one vertex of us,vs. We claim that every multiresolving set of T contains three vertices of u1,us,v1,vs. Suppose, contrary to our claim, that there is a multiresolving set S of T containing only one of u1,v1 and one of us,vs. By Observation 1, we may assume, without loss of generality, that W⊂S. If u1,us∈S, then mru1S=mrw2S, which is impossible. If u1,vs∈S, then mru1S=mw2S, a contradiction. If v1,us∈S, then mrusS=mrws−1S, producing a contradiction. If v1,vs∈S, then mrv1S=mrvsS, which is also impossible. Therefore, every multiresolving set of T has cardinality at least Ψ+3. Hence, dimMT=Ψ+3 and so W∪u1,v1,vs is a multibasis of T.
LetT be a symmetric caterpillar cak1,k2,…,ks with ki=1 for some integer i with 2≤i≤s−1. If T−vi is not a path, then by applying Theorems 5 and 8, dimMT−vi=dimMT. This observation provides us with the following more general result whose proof is straightforward and is therefore omitted.Corollary 2.
Fors≥3, let T be a symmetric caterpillar cak1,k2,…,ks with a second end-set ΨT and let T′ be a caterpillar cal1,l2,…,ls that is a subgraph of T and is not a path, with a second end-set ΨT′. If ΨT′=ΨT, then dimMT′=dimMT.


## 4. Final Remarks

A subdivisionT′ of a symmetric caterpillar T is a graph that is obtained from T by inserting vertices of degree 2 into some, all or none of the edges of T. It would be interesting to study the multibasis of the subdivision T′ of T.



---

*Source: 5210628-2020-06-24.xml*