# Locating-Total Domination Number of Cacti Graphs

Authors: Jianxin Wei; Uzma Ahmad; Saira Hameed; Javaria Hanif
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

For a connected graphJ, a subset W⊆VJ is termed as a locating-total dominating set if for a∈VJ,Na∩W≠ϕ, and for a,b∈VJ−W,Na∩W≠Nb∩W. The number of elements in a smallest such subset is termed as the locating-total domination number of J. In this paper, the locating-total domination number of unicyclic graphs and bicyclic graphs are studied and their bounds are presented. Then, by using these bounds, an upper bound for cacti graphs in terms of their order and number of cycles is estimated. Moreover, the exact values of this domination variant for some families of cacti graphs including tadpole graphs and rooted products are also determined.


---

## Body

## 1. Introduction

LetJ=V,E be a simple undirected and connected graph with vertex set V=VJ and edge set E=EJ. The number of vertices in J is called the order of J. The set of vertices in V adjacent to any vertex v is called the open neighbourhood of v in V, denoted by NJv, and the set NJv∪v is called the closed neighbourhood of v in V, denoted by NJv. A vertex of degree one is called leaf (pendant) and its unique neighbouring vertex is called support vertex. A set W ⊆ V (J) is said to be a dominating set of J if every vertex in V − W has nonempty open neighbourhood in W and furthermore if Na∩W≠ϕ for every vertex a∈VJ, then this set W is referred to as a total dominating set in J. A total dominating set W with the additional condition that every pair of distinct vertices outside W have distinct open neighbourhood in W is known as a locating-total dominating set, abbreviated as LTD-set. The smallest dominating, total dominating, and locating-total dominating sets of J are denoted by γ (J)-set,γtJ-set, and γtLJ-set, respectively, and their cardinalities are known as domination, total domination, and locating-total domination numbers, respectively.A path and cycle havingm vertices are denoted by Pm and Cm. A simple connected graph having no cycle is a tree. A graph is a unicyclic or bicyclic graph if it contains exactly one cycle or two cycles, respectively. A graph in which any two distinct cycles have maximum one vertex in common is termed as a cactus. A tadpole graph is obtained by joining a leaf (pendant) vertex of path to a vertex of a cycle through an edge. For connected graphs K and L, the rooted product of K by LK⊙L is obtained by considering |K| copies of L and identifying the i-th vertex of L with the root vertex of i-th copy of L. The idea of locating-total domination and differentiating-total domination was presented first by Haynes et al. [1]. They studied these variants of domination for trees and estimated a bound on this class. The differentiating-total and locating-total domination numbers of path graphs are also determined. The improved new bound for locating-total dominating number of trees is presented by Chen and Sohn [2]. They also gave the sharpness of these bounds and identified the trees achieving these bounds. The different versions of locating-total domination number for different classes of graphs are investigated in [3–5]. The bounds on locating-total domination number for different types of products are studied in [6, 7]. A new bound of locating-total domination number using annihilation number of a tree was presented by Ning et al. [8]. They also identified the trees attaining this bound. In this paper, locating-total domination number of unicyclic and bicyclic graphs is investigated and their upper bounds are given. Consequently, using these bounds, an upper bound for cacti graphs is presented. Moreover, the exact values of this domination variant for some classes of cacti graphs are computed. In particular tadpole graphs, rooted products of path by cycle graph and cycle by path graph are computed.


## 2. Bounds of Locating-Total Domination Number of Cacti Graphs

Theorem 1 (see [2]).
For a treeℑ having r ≥ 3 vertices and l pendant vertices, one has(1)γtLℑ≤r+l2.Proposition 1 (see [9]).
TheγtL-set of a graph J must include all the support vertices of J.
A unicycle graphU having r ≥ 3 vertices can be obtained by connecting any two nonadjacent vertices of a tree ℑ having r ≥ 3 vertices by an edge.Lemma 1.
LetW be a γtL-set of a tree ℑ with order r ≥ 4 and l′ pendant vertices. Let U be the unicyclic graph of order r ≥ 4 with l pendant vertices constructed by joining any two nonadjacent vertices u,v∈Vℑ through an edge. If either both belong to W or none of them belongs to W, then(2)γtLU≤r+l+22.Proof.
It is easy to see that theγtL-set of a graph G′ obtained by adding edges between two vertices of γtL-set or between two vertices not in γtL-set of a graph G is the same as that of γtL-set of G. This implies that W also becomes a γtL-set for U. Hence, by Theorem 1, we have(3)γtLU=W=γtLℑ≤r+l′2.
Two cases arise:Case 1: Assume that one of them is a pendant vertex. If exactly one is a pendant vertex, thenl=l′−1 and by (3),(4)γtLU≤r+l+12<r+l+22.But if both are leaves, thenl=l′−2 and by (3),(5)γtLU≤r+l+22.Case 2: Now assume none of them is a leaf; then,l′=l and by (3),(6)γtLU≤r+l2<r+l+22.Theorem 2.
LetU be a unicycle graph having r ≥ 3 vertices and l pendant vertices. Then,(7)γtLU≤r+l+32.Proof.
Letℑ be a tree of order r with l’ leaves and u,v∈Vℑ be its two nonadjacent vertices such that unicycle U is obtained from ℑ by joining u and v. Let W be a γtL-set of ℑ. Now the vertices u and v may belong to W or not. If both vertices u and v belong to W or both vertices u and v do not belong to W, then by Lemma 1, it is easy to see that W becomes γtL-set for U and(8)γtLU=W=γtLℑ≤r+l+22.
Now supposeu∉W,v∈W, and v is a pendant vertex. Then there exists support vertex s such that v∼s. By Proposition 1, s ∈ W. Now as v is a pendant, Nv∩W=s in ℑ, and v is not adjacent to any vertex of VT−W. Also, u is adjacent to some vertex v≠w∈W so that in U,w,v⊆Nu∩W. As in U, v is not adjacent to any other vertex of VU−W except u, so Nu∩W≠Ny∩W for all y∈VU−W. Moreover, for all u≠y,z∈VU−W,Ny∩W≠Nz∩W because for all u≠y,z∈VT−W,Ny∩W and Nz∩W remain the same in both ℑ and U. This further implies that, in this case, W again becomes γtL-set for U. Therefore, by Theorem 1 and the fact that either l=l′−1 or l=l′−2, we have(9)γtLU=W=γtLℑ≤r+l′2≤r+l+22.
Finally, suppose that allu∈W,v∉W, and v is not a leaf. Then, W∪v is LTD-set for U. Therefore, by Theorem 1, we have(10)γtLU≤W+1=γtLℑ+1≤r+l′2+1.
Ifu is a pendant vertex, then l=l′−1 and by (10), we have(11)γtLU≤r+l+12+1=r+l+32.
But ifu is not a pendant vertex, then l′=l and by (10)(12)γtLU≤r+l2+1=r+l+22.
The result follows from (8), (9), (11), and (12).
If in a unicycle graphU with cycle length m, all the edges of its unique cycle are removed, then resulting graph is a disconnected graph which is union of m disjoint subtrees Ti, where i=1,……,m. Each subtree Ti is a maximal subtree of U containing only one cycle vertex. A bicyclic graph B can be constructed from a noncorona unicyclic graph U by choosing any two nonadjacent vertices u,v∈VTi⊆VU for some i (i.e., u and v must be in one subtree Ti of U) and joining the vertices must contain at least one cycle edge, u and v through an edge. It is easy to see that any path between vertices of two distinct subtrees.Lemma 2.
Consider a unicyclic graphU with r > 5 vertices and l′ leaves and γtL-set W′. Choose any two nonadjacent vertices u and v from maximal subtree Ti of U containing exactly one cycle vertex such that either both belong to W′ or none of them belongs to W′. Let B be a bicyclic graph having r > 5 vertices and l pendant vertices obtained by connecting u,v∈VU through an edge. Then,(13)γtLB≤r+l+52.Proof.
The proof is the same as that of Lemma1.Theorem 3.
For bicyclic graph B with orderr > 4 and l pendant vertices, one has(14)γtLB≤r+l+62.Proof.
LetU be the unicyclic graph of order r > 4 with l′ pendant vertices and u,v∈VTi⊆VU be its two nonadjacent vertices, where Ti is maximal subtree of U containing exactly one cycle vertex. Then, bicyclic graph B can be obtained from U by joining u and v. Let W′ be a γtL-set of U. Now the vertices u and v may belong to W′ or not.
The result follows by using Lemma2 and the similar arguments as used in Theorem 2.
Now, as an extension of Theorems2 and 3, an upper bound for locating-total domination number of cacti graphs is appraised as follows.Theorem 4.
Letζ be cacti with r vertices, l pendant vertices, and q cycles. Then, one has(15)γtLζ≤r+l+3q2.Proof.
We prove this by making use of mathematical induction onq. If q = 1, 2, then the desired result follows immediately by Theorems 2 and 3. Hence, we have a base for induction. Now assume that the bound is satisfied for any cacti graph having order r and containing q − 1 cycles. Now a cactus ζ with order r, leaves l, and cycles q can be obtained from a cactus ζ′ of order r with l′ leaves, q − 1 cycles, and γtL-set W in one of the following three ways:Select any two pendant verticesu and v of ζ′ such that the shortest path between u and v must not have any cycle edge. Now if the vertices u and v are connected by an edge, we get a cactus ζ. In this case, we can see that the set W is also LTD-set of ζ by using similar arguments as used in Theorems 2 and 3. Now here l′=l+2 and using induction hypothesis, we have(16)γtLζ≤γtLζ′≤r+l′+3q−12=r+l+2+3q−32<r+l+3q2.Select a pendant vertexu and a nonpendant vertex v of ζ′ such that the shortest path between u and v does not include any cycle edge. Now if the vertices u and v are connected by an edge, we get a cactus ζ. In the case, when u∉W,W∪u is LTD-set of ζ; otherwise,W is LTD-set for ζ by using similar arguments as used in Theorems 2 and 3. Now here l′=l+2 and using induction hypothesis, we have(17)γtLζ≤γtLζ′+1≤r+l′+3q−12+1=r+l+2+3q−3+22=r+l+3q2.Select any two nonpendant verticesu and v of ζ′ such that the path between u and v does not include any cycle edge. Now if the vertices u and v are connected by an edge, we get a cactus ζ. In the case, when exactly one of the u or v, say u, belongs to W, then W∪v is LTD-set; otherwise, W is LTD-set for ζ by using similar arguments as used in Theorems 2 and 3. Now here l′=l and using induction hypothesis, we have(18)γtLζ≤γtLζ′+1≤r+l′+3q−12+1=r+l+2+3q−3+22<r+l+3q2.
Hence, the result follows.


## 3. Tadpole and Rooted Product Graphs

In this section, locating-total domination number for few cacti graphs is determined. In particular, tadpole graphs (unicyclic graphs), rooted product of cycle by path (unicyclic graphs), and rooted product ofPq by Cm(cacti graph with q cycles) are investigated.Theorem 5 (see [1]).
Forq≥3,γtLPq=⌊q/2⌋+⌈q/4⌉−⌊q/4⌋.Theorem 6 (see [4]).
Forq≥3,γtLCq=⌊q/2⌋+⌈q/4⌉−⌊q/4⌋.Remark 1.
The locating-total domination number ofCq and Pq for different values of q can be simplified as(1)
γtLCq=γtLPq=q/2 if q≡0mod4.(2)
γtLCq=γtLPq=q/2+1 if q≡2mod4.(3)
γtLCq=γtLPq=q+1/2 if q is odd.
LetTq1,q2rq≥3 be a tadpole having r=q1+q2 vertices and is formed by connecting a vertex of cycle Cq1 to pendant vertex of path by an edge.Theorem 7.
Letq1 be odd positive integer. Then, one has(19)γtLTq1,q2r=r2,ifq2≡1mod4,r+12,ifq2≡0,2mod4,r2+1,ifq2≡3mod4,q1≡3mod4,r2,ifq2≡3mod4,q1≡1mod4.Proof.
Suppose thatPq2: a1 ⟶ a2 ⟶ a3 ⟶  ···  ⟶ aq2 is connected through aq2 to a cycle vertex u of Tq1,q2r. Let W be a γtL-set for Tq1,q2r. As |W| is minimum, therefore a2 being support vertex by Proposition 1 and a3 being its unique neighbouring vertex by definition of locating-total dominating set must belong to W. Consequently, a4 and a5 can be excluded from W and then the next two consecutive vertices belong to W. By continuing this process, we can see that for j=2,3mod4,a∈W and for j=0,1mod4,aj∉W.Case 1: Supposeq2 ≡ 1 (mod4). If q2 = 1, then vq2∈Tq1,q2r is a pendant vertex and u is a support vertex. Thus, vq2,u∈W and(20)γtLTq1,1r=γtLCq1=r2.But ifq2 > 1, then as q2 ≡ 1 (mod4), aq2,aq2−1∉W and aq2−2,aq2−3 ∈ W.Consequently, totalq2−1/2 vertices of Pq2 belong to W. Since aq2, aq2−1∉W, therefore u ∈ W. Thus, we have(21)γtLTq1,q2r=γtLCq2+q2−12=r2.TheγtL-set of tadpole graph Tq1,q2r for q ≡ 1 (mod4) is represented by black vertices in Figure 1.Case 2: Supposeq2 ≡ 2 (mod4). If q2 = 2, then aq2 is a support vertex. Therefore, aq2 ∈ W. Also, using the definition of LTD-set, u ∈ W. This implies that q1+1/2 cycle vertices must belong to W and hence we have(22)γtLTq1,2r=q1+12+1=r+12.But ifq2 > 2, then as q2 ≡ 2 (mod4), therefore aq2 ∈ D and aq2−1, aq2−2∉W. Consequently, q2/2 path vertices belong to W. Also, since aq2 ∈ W and aq2−1, aq2−2∉W, therefore u ∈ W which implies that q1+1/2 cycle vertices must be in W. Hence,(23)γtLTq1,q2r=q1+12+q22=r+12.TheγtL-set of tadpole graph Tq1,q2r for q ≡ 2 (mod4) is represented by black vertices as shown in Figure 2.Case 3: Now assumeq2 ≡ 0 (mod4). If q2 = 0, then we have(24)γtLTq1,0r=γtLCq1=r+12.But ifq2 > 0, then as q ≡ 0 (mod4) and |W| is minimum, so aq1∉W and aq2−1, aq2−2∈ W. Consequently, q2/2 path vertices lie in W. Also, since aq2∉W and aq2−1, aq2−2∈W and u can be excluded from W. This implies that q1+1/2 cycle vertices must lie in W and hence(25)γtLTq1,q2r=q1+12+q22=r+12.TheγtL-set of tadpole Tq1,q2r for q2≡0mod4 is shown in Figure 3 with black vertices.Case 4: Finally, assume thatq2 ≡ 3 (mod4). If q2 = 3, then a2 being support vertex and a3 being its neighbouring vertex lie in W. But then u can be taken out of W. Moreover, for q1≡3mod4,q1+1/2 cycle vertices lie in W and hence(26)γtLTq1,3r=q1+12+2=r2+1.
On the other hand, ifq1 ≡ 1 (mod4), then q1−1/2 cycle vertices belong to W and we have(27)γtLTq1,3r=q1−12+2=r2.
Now ifq2 > 3, then as q2 ≡ 3 (mod4); therefore, aq2, aq2−1 ∈ W and aq2−2,aq2−3∉W. Consequently, q2+1/2 path vertices lie in W. Also, as aq2, aq2−1 ∈ W, and u can be excluded from W. But then the vertices which lie in γtLCq1 must lie in W. Moreover, if q1 ≡ 3 (mod4), then q1+1/2 cycle vertices are in W. Thus, we have(28)γtLTq1,q2r=q1+12+q2+12=r2+1,whereas if q1 ≡ 1 (mod4), then q1−1/2 cycle vertices belong to W and we have(29)γtLTq1,q2r=q1−12+q2+12=r2.
TheγtL-set of tadpole Tq1,q2r for q2≡3mod4 is shown in Figure 4 with black vertices.Figure 1
TadpoleTq1,q2r for q2 ≡ 1 (mod4).Figure 2
TadpoleTq1,q2r for q ≡ 2 (mod4).Figure 3
TadpoleTq1,q2r for q2 ≡ 0 (mod4).Figure 4
TadpoleTq1,q2r for q2≡3mod4.Theorem 8.
Letq1 be an even integer. Then one has(30)γtLTq1,q2r=r+12,ifq2≡1,3mod4,r2,ifq2≡2mod4,r2,ifq2≡0mod4,q1≡0mod4,r2+1,ifq2≡0mod4,q1≡2mod4.Proof.
LetW be a γtL-set for Tq1,q2r. As |W| is minimum, therefore a2 being support vertex by Proposition 1 and a3 being its unique neighbouring vertex by definition of locating-total dominating set must belong to W. Consequently, a4 and a5 can be excluded from W and then the next two consecutive vertices belong to W. By continuing this process, we can see that for j ≡ 2, 3 (mod4), aj∈W and for j ≡ 0, 1 (mod4), aj∉W.Case 1: Supposeq2 ≡ 1 (mod4). If q2 = 1, then aq2∈Tq1,q2r is a pendant vertex and u is a support vertex. Thus, aq2,u ∈ W and(31)γtLTq1,1r=q12+1=r+12.TheγtL-sets of tadpoles T4,15 and T6,17 are shown in Figure 5 with black vertices. But if q2 > 1.Then asq2 ≡ 1 (mod4), aq2,aq2−1∉ W and aq2−2,aq2−3 ∈ W. Consequently, total q2−1/2 path vertices belong to W. Further, since aq2,aq2−1∉W, therefore u ∈ W. Thus, q1/2+1 cycle vertices lie in D and consequently,(32)γtLTq1,q2r=q12+1+q2−12=r+12.Case 2: Supposeq2 ≡ 3 (mod4). If q2 = 3, then a2 being support vertex and a3 being its neighbouring vertex lie in W. And u can be excluded from W. This implies that q1/2 cycle vertices must lie in W, and hence, we have(33)γtLTq1,3r=q12+2=r+12.TheγtL-set of tadpoles T4,37 and T6,39 are shown in Figure 6 with black vertices.But ifq2 > 3, then as q2 ≡ 3 (mod4), so aq2,aq2−1 lie in W, whereas aq2−2,aq2−3∉W. Consequently, q2+1/2 path vertices belong to W. Further, as aq2,aq2−1 lie in W so u can be taken out of W. Thus, q1/2 cycle vertices lie in W so that(34)γtLTq1,q2r=q12+q2+12=r+12.Case 3: Now supposeq2 ≡ 2 (mod4). If q2 = 2, then aq2 being a support vertex belongs to W. This further implies that u ∈ W. Hence, q1/2 cycle vertices lie in W, and consequently,(35)γtLTq1,2r=q12+1=r2.TheγtL-set of tadpoles T4,26 and T6,28 are shown in Figure 7 with black vertices.On the other hand, ifq2 > 2, then aq2 ∈ W but aq2−1, aq2−2∉W. This implies that q2/2 path vertices are included in W along with cycle vertex u. Consequently, q1/2 cycle vertices lie in W and we have(36)γtLTq1,q2r=q12+q22=r2.Case 4: Finally assumeq2 ≡ 0 (mod4). It is easy to see that if q2 = 0, then Tq1,0r≅Cq1 and r = q1.
Hence,(37)γtLTq1,0r=γtLCq1.
Using Remark 3, we have(38)γtLTq1,0r=q12,ifq1≡0mod4,q12+1,ifq1≡2mod4.
Asr = q1, so we have(39)γtLTq1,0r=r2,ifq1≡0mod4,r2+1,ifq1≡2mod4.
But ifq2 > 0, then aq2∉W and aq2−1, aq2−2 ∈ W. This shows that q2/2 path vertices belong to W. Also, since aq2∉W and aq2−1, aq2−2 ∈ W, u must be in W. Hence, the vertices that belong to γtLCq1 must lie in W. Hence, we have(40)γtLTq1,q2r=q22+γtLCq1.
Again, using Remark 3, we have(41)γtLTq1,q2r=q22+q12,ifq1≡0mod4,q22+q12+1,ifq1≡2mod4.
Thus,(42)γtLTq1,q2r=r2,ifq1≡0mod4,r2+1,ifq1≡2mod4.
In Theorem9, the rooted product Pq2⊙Cq1 is computed. Any cycle vertex can be considered as root vertex.Figure 5
The tadpolesT4,15 and T6,17.
(a)(b)Figure 6
The tadpolesT4,37 and T6,39.
(a)(b)Figure 7
The tadpolesT4,26 and T6,28.
(a)(b)Theorem 9.
For positive integersq1 ≥ 3 and q2 ≥ 1, one has(43)γtLPq2⊙Cq1=γtLCq1,ifq2=1,q2γtLCq1,ifq1≡0,3mod4,q2γtLCq1−1+q22,ifq1≡1mod4,q2γtLCq1−2+q2,ifq1≡2mod4.Proof.
Ifq2 = 1, then Pq2⊙Cq1≅Cq1 and γtLPq2⊙Cq1=γtLCq1. Now we may suppose q2 ≥ 2.
Then four cases arise:Case 1: Supposeq1≡0mod4, that is, q1=4k for integer k > 0. The graph Pq2⊙Cq1 contains q2 mutually disjoint cycles Cq1i, where i = 1,·..., q2. For each i, cycle Cq1i consists of 4k vertices, namely, vji where j = 1, …, 4k. Take v1i as root vertex of each cycle. The 4k vertices in each cycle are divided into k sets such that each set contains four consecutive vertices of cycle. From each set, the middle two vertices can be taken as elements of minimum LTD-set for each Cmi . Let this minimum LTD-set of Cmi. Then Wi=v2i,v3i,v6i,v7i,…,v4k−2i,v4k−1i with |Wi| = 2k = γtLCmi. These 2k vertices in each Wi are shown in Figure 8 as black vertices.Now the root verticesv1i from each Cmi are actually the path vertices and are locating totally dominated by the elements of Wi for each i. Hence, all the vertices of Pq2⊙Cq1 are locally dominated by ∪i=1q2Wi. Also, this set is minimum by construction. Thus,(44)γtLPq2⊙Cq1=q2γtLCq1.Case 2: Supposeq1≡1mod4, that is, q1=4k+1, for integer k > 0. Let v1i be the root vertex of cycle Cq1i for each i. The graph Cq11−v11 contains 4k vertices and these 4k vertices are divided into k sets. Now we select two middle vertices from each set. Then, all 4k vertices of Cq11−v11 are locating totally dominated by 2kchosen vertices. Since v11 does not have a neighbour in the selected LTD-set of Cq11, therefore, v12 must be a LTD-vertex. The graph Cq12−v12 also contains 4k vertices and these 4k vertices are again divided into k sets and all are locating totally dominated by 2k vertices by selecting the first and last vertices from each set. Now we are interested in minimum LTD-set; v13 may not be an LTD-vertex. By continuing in this way, we can see that if i is odd then v1i is not an LTD-vertex otherwise v1i is an LTD-vertex. This along with the fact that path vertices are root vertices implies that all the vertices of graph are locating totally dominated by a set W of smallest cardinality. We note that if the path (root) vertex is not an LTD-vertex, then associated cycle has 2k vertices in W and otherwise each cycle has 2k + 1 vertices in W. Hence,(45)γtLPq2⊙Cq1=q2γtLCq1−1+q22.TheγtL-set of Pq2⊙Cq1 for q1 ≡ 1 (mod4) is shown in Figure 9 with black vertices.Case 3: Supposeq1 ≡ 2 (mod4) such that q1 = 4k + 2 and k > 0 is an integer. In a similar manner as in Cases 1 and 2, we divide the vertices of each Cq1i−v11,ai, where ai is neighbouring vertex of root vertex into k sets. For each i, all the vertices of Cq1i−v11,ai are locating totally dominated by 2k chosen vertices (middle two vertices in each set). The vertices v1i and ai for all i can be locating totally dominated if we include all the root vertices. This implies that(46)γtLPq2⊙Cq1=q2γtLCq1−2+q2.TheγtL-set of Pq2⊙Cq1 for q1 ≡ 2 (mod4) is shown in Figure 10 with black vertices.Case 4: Finally, supposeq1 = 4k + 3, where k > 0 is an integer. Here, the vertices of Cq1i−v11,ai,bi, where ai and bi are consecutive two vertices of root vertex v1i on cycle, are divided into k sets. Again for each i, all the vertices Cq1i−v11,ai,bi are locating totally dominated by 2k chosen vertices (first two vertices in each set). The vertices v11,ai,bi for all i can be locating-total dominated by selecting two of them except root vertex. Therefore, in this case, we have(47)γtLPq2⊙Cq1=q2γtLCq1.
TheγtL-set of Pq2⊙Cq1 for q1 ≡ 3 (mod4) is shown in Figure 11 with black vertices.
In the following Theorem10, the rooted product Cq1⊙Pq2 is computed. Here, we select pendant vertex of path as root vertex.Figure 8
The rooted productPq2⊙Cq1 for q1 ≡ 0 (mod4).Figure 9
The rooted graphPq2⊙Cq1 for q1 ≡ 1 (mod4).Figure 10
The graphPq2⊙Cq1 for q1 ≡ 2 (mod4).Figure 11
The graphPq2⊙Cq1 for q1 ≡ 3 (mod4).Figure 12
The productCq1⊙Pq2 for q2 ≡ 0 (mod4).Figure 13
The graphCq1⊙Pq2 for q2 ≡ 1 (mod4).Figure 14
The productCq1⊙Pq2 for q2 ≡ 2 (mod4).Theorem 10.
Forq1 ≥ 3 and q2 ≥ 2 and by taking pendant vertex of Pq2 as root vertex, one has(48)γtLCq1⊙Pq2=q1γtLPq2,ifq2≡0,2mod4,q1γtLPq2−1+γtLCq1,ifq2≡1mod4,q1γtLPq2−3+2q1,ifq2≡3mod4.Proof.
Case 1: Supposeq2 ≡ 0 (mod4), such that q2 = 4k and k > 0. The rooted product Cq1⊙Pq2 consists of mutually disjoint q1 paths Pq2i for i = 1, ..., q1. Suppose v1i is the root vertex of Pq2i for i = 1, ..., q1. The 4k vertices of Pq2i are split into k sets, each containing four consecutive vertices. Then the collection of middle two vertices from each set in every path gives the LTD-set for graph Cq1⊙Pq2 which is also minimum one:(49)γtLCq1⊙Pq2=q1γtLPq2.TheγtL-set of Cq1⊙Pq2 for q2 ≡ 0 (mod4) is represented by black vertices in Figure 12.Case 2: Assumeq2 ≡ 1 (mod4) such that q2 = 4k + 1 and k > 0. Let voi be the root vertex in each path Pq2i of Cq1⊙Pq2. Consider Pq2i−voi consisting of 4k vertices and all the vertices in Pq2i−voi can be locating totally dominated by 2k chosen vertices (two middle vertices from each set). Since all the paths Pq2i for i = 1,···, q1 are mutually disjoint, therefore ∪iq1Pq2i−voi is minimum locating-total dominated set consisting of 2k⋅q1 vertices. Therefore,(50)γtLCq1⊙Pq2=2kq1+γtLCq1=q1γtLPq2−1+γtLCq1.TheγtL-set of Cq1⊙Pq2 for q2 ≡ 1 (mod4) is represented by black vertices as shown in Figure 13.Case 3: Now suppose thatq2 ≡ 2 (mod4) such that q2 = 4k + 2. Here, each Pq2i for i = 1,···, q1 consists of 4k + 2 vertices. All of them except the root and its neighbouring vertex are locating totally dominated by 2k chosen vertices from each path as in the previous cases. These chosen vertices must belong to γtL-set. To obtain, minimum LTD-se for rooted product, all the root vertices are also included. Hence,(51)γtLCq1⊙Pq2=2kq1+q1=q1γtLPq2−2+q1.TheγtL-set of Cq1⊙Pq2 for q2 ≡ 2 (mod4) is represented by black vertices in Figure 14.Case 4: The caseq2 ≡ 3 (mod4) is dealt in a similar manner as in previous cases. Thus, we have(52)γtLCq1⊙Pq2=q1γtLPq2−3+2q1.TheγtL-set of Cq1⊙Pq2 for q2 ≡ 3 (mod4) is shown in Figure 15 with black vertices.Figure 15
The graphCq1⊙Pq2 for q2 ≡ 3 (mod4).


## 4. Conclusion

In this paper, the upper bounds for locating-total domination number of unicyclic and bicyclic graphs are obtained. It is shown that, for unicyclic graph U of orderr and leaves l, γtLU≤r+l+3/2 and for bicyclic graph B of order r and leaves l, γtLB≤r+l+6/2. These bounds are then generalized for cacti graphs of order n having q cycles as r+l+3q/2. Also, the exact value of locating-total domination numbers for some cacti graphs is determined. For tadpole graph Tq1,q2r, it is found that locating-total dominating number is r/2, r+1/2, or r/2+1 depending upon the parity of r and values of q1 and q2. The locating-total dominating number of rooted product of Cq1 by Pq2 in terms of q1 and γtLPq2 is computed. Similarly, locating-total dominating number of rooted products of Pq2 by Cq1 in terms of q2 and γtLCq1 is also determined. It is still an open problem to find the sharpness of estimated bounds of locating-total dominating number for cacti graphs.



---

*Source: 6197065-2020-10-19.xml*