Ratio Mathematica Volume 44, 2022 The Detour Domination and Connected Detour Domination values of a graph R. V. Revathi 1 M. Antony 2 Abstract The number of -sets that belongs to in G is defined as the detour domination value of indicated by for each vertex . In this article, we examined at the concept of a graph’s detour domination value. The connected detour domination values of a vertex represented as , are defined as the number of -sets to which a vertex belongs to G. Some of the related detour dominating values in graphs’ general characteristics are examined. This concept’s satisfaction of some general properties is investigated. Some common graphs are established. Keywords: domination number; detour number; detour domination value; connected detour domination value; etc. 2010 AMS subject classification: 05C15, 05C69 3 1 Register Number 19133232092002, Research Scholar, Department of Mathematics, St. Jude’s College, Thoothoor - 629 176, Affiliated to Manonmaniam Sundaranar University, Abishekapatti, Tirunelveli - 627 012, Tamil Nadu, India; revathi87gowri@gmail.com. 2 Associate Professor, Department of Mathematics, St. Jude’s College, Thoothoor - 629 176, Affiliated to Manonmaniam Sundaranar University, Abishekapatti, Tirunelveli - 627 012, Tamil Nadu, India; antony.michael@yahoo.com 3 Received on June 9 th, 2022. Accepted on Aug 10 th , 2022. Published on Nov 30th, 2022. doi: 10.23755/rm.v44i0.908. ISSN: 1592-7415. eISSN: 2282-8214. ©The Authors.This paper is published under the CC-BY licence agreement. 205 mailto:revathi87gowri@gmail.com R.V. Revathi, and M. Antony 1. Introduction Graph having the type G = (V, E) is a finite, undirected connected graph without loops or numerous edges. The order and size of the letter G are represented by the characters n and m, respectively. We refer to [3] for the fundamental terms used in graph theory. If uv is an edge of G, then two vertices u and v are said to be adjacent. If two edges of G connect a vertex, they are said to be adjacent. The distance between two vertices and v in a connected graph is thelength of a shortest - path in . A u-v geodesic is a u-v path of length . The longest - path in G is also referred to as detour distance between two vertices u and v in a linked graph G from u to v. A - detour is a - path of length . If x is a vertex of P that also contains the vertices u and v, then x is said to lie on a - detour. Every vertex of G is contained in a detour connecting some pair of vertices in S, which is the definition of a detour set of G. Any detour set of order (G) is referred to as a minimum detour set of G or a -set of G. The detour number (G) of G is the minimum order of a detour set. These ideas have been researched in [4, 5, 6]. If for every v V \ D is adjacent to a vertex in D, then the set D⊆ V is a dominant set of G. If no subset of a dominating set D is a dominating set of G’s, then D is said to be minimal. The symbol denotes the domination number of G, which is the least cardinality of a minimal set of G dominating sets. In [4], the graph's domination number was studied. If a set S is both a detour and a dominating set of G’s, then it is referred to as a detour dominating set of G. Any detour dominating set of order is referred to as a – set of G. The detour domination number of G is the minimal order of its detour dominating set. In [8], the detour domination number of a graph studied. If a set S is a detour dominating set of G and its induction by S is connected, the set S ⊆ V(G) is referred to as a connected detour dominating set of . Any connected detour dominating set with order is referred to as a - set of G. The connected detour domination number of of G is the maximum order of its connected detour dominating sets. In [8,9], the connected detour domination number of a graph was investigated. The subsequent theorem is applied thereafter. Theorem 1.1[3] Every detour set of a connected graph G contains each end vertex. Theorem 1.2[3] Let be a connected graph Then if and only if Theorem 1.3[3] Let be a connected graph of order Then if and only if 206 The detour domination and connected domination values of a graph 2.The Detour Domination Value of a Graph Definition 2.1. For each vertex we define the detour domination value of denoted by to be the number of -sets to which belongs to Example 2.2. In relation to the graph G in Figure 2.1, = , = = = = , = are the onlysix minimum -sets of such that , , Theorem 2.3. For the complete graph = ( for each Proof. Since any two sets of G's vertices is the -set of thus Since each vertex of belongs to exactly -sets, it follows that for each ∎ Theorem 2.4. For a star = ( for each Proof. We have . Let S represent the set of all of the end vertices in G. Then is the unique -set of Thus Therefore for each ∎ Theorem 2.5. For the complete bipartite graph with bipartite sets and and If then If for any in Figure 2.1 207 R.V. Revathi, and M. Antony If with then Proof. Let and be the two bipartite sets of Since any two adjacent vertices of is a -sets of it follows that if If then it has only one a set of such that If then it only one -set of such that . If then any vertex in belongs to a -set of hence Also if ,then any vertex in belongs to a -set thus for If then for any in If with , then , ∎ Theorem 2.6.For the wheel graph , and Proof. Let and . Let Then , , , , , , are -sets of such that , , Let Then any two adjacent vertices of is a -set of so that for , hence lies in exactly three -set of so that for all Since is adjacent to vertices of ∎ Theorem 2.7. For the cycle graph , Proof. Let . Let where Here a -set comprises and is fixed by the choice of the first There exists exactly one -set containing the vertex and there are two -sets omitting the vertex such as containing the vertex and containing the vertex . Thus Let where Here a -set is constituted in exactly one of the following two ways. i) comprises ’s and one ii) comprises ’s 208 The detour domination and connected domination values of a graph Case(i) Note that is fixed by the choice of the single choosing a in the same as choosing its initial vertex in the counter clockwise order. Hence Case(ii) It is clear that each dominates three vertices, exactly there are two vertices, say and each of whom is adjacent to two distinct ’s in . And is fixed by the placements of and There are ways of choosing Consider the (a sequence of slots) obtained as a result of cutting from the centered about vertex. may be placed in the first slot of any of the . As the order of selecting the two vertices and is immaterial . Summing over the two disjoint cases, we get Let where Here a -set comprises of only and is fixed by the placement of the only vertex which is adjacent to two distinct in Hence ∎ 3. The Connected Detour Domination Value of a Graph Definition 3.1. For each vertex we define the connected detour domination values of denoted by to be the number of -sets to which belongs to Example 3.2. For the graph given in Figure 3.1, = , = = = = = , = = are the only eight minimum -sets of such that , , and Figure 3.1 209 R.V. Revathi, and M. Antony Proposition 3.3. Let be a graph with vertices without cut vertices and Then and and equality holds if and only if . Proof. Let be a universal vertex of . Let Then is a -set of so that Since is a universal vertex of belongs to every -set of Since contains at most -sets, Let . Hence it follows that belongs to every -set of Therefore The converse is clear. ∎ Theorem3.4. For and Proof. Let Then and are the -sets of so that . As is vertex transitive for all . Since belongs to -sets of it follows that for all ∎ Theorem3.5. For and for each vertex . Proof. Since is the unique -sets of the results follow theorem. ∎ Theorem3.6. For the complete graph for each vertex . Proof. Since any two set of vertices of is the -set of , it follows that Since each vertex of belongs to exatly -sets, it follows that for each vertex . ∎ Theorem3.7. For the wheel graph and Proof. Let and Let Then are the - sets of such that and . Let Then any two adjacent vertices of is a -sets of so that for lies in excatly three - sets of so that for all . Since is adjacent to vertices of ∎ Theorem3.8. Let and and 210 The detour domination and connected domination values of a graph Then for is odd and and for is even and Proof. Let and Case (i) is odd. are the only three -sets of such that so that . Case (ii) is even. arethe only four -sets of so that , and . ∎ Theorem3.9. Proof. Let be a -sets of of cardinality where if then and any two adjacent vertices form a -set i.e. , are all possible -sets of . If there is a unique -set So let By lemma 2.2 either or (and not both). Let . As to maintain connectedness of and to dominate we have In the same way, Thus Since contains elements, let the other 2 vertices in be To dominate and one of and (say must be either or Similarly is either or Since there are two choices each for and such that forms a -set, the number of -sets containing is 4. Similarlythe number of -sets containing is 4. Hence by lemma 2.2, we get for ∎ Theorem3.10. Let be a rectangular grid with and let or If then for all If then and , If then Proof. The proof is clear for and theorem 2.10, so we assume that Let be a vertex in Case 1: [ Let then using the line of proof of Theorem 3.10, the -sets containing are precisely those where and is either or i.e, Same for the case when or or . 211 R.V. Revathi, and M. Antony Case 2: [ Let Note that any connected dominating set contains either Also total number of minimum connected dominating sets is 8, out of which only two does not contain namely and Thus Now,as there exist isomorphisms which maps to , respectively, by proposition 2.2, we have . Case 3: [ In this case, from the proof of Theorem 2.10 we have . References [1] Buckley and F.Harary, Distance in Graph, Addition-Wesly-wood city, CA, (1990). [2] G. Chartrand, G. Johns and P. Zhang, On the detour number and geodetic number of a graph, Ars combinatoria, 72(2004), 3-15. [3] G. Chartrand, G. Johns and P. Zhang, The detour number of a graph, Utilitas Mathematica, 64(2003), 97-113. [4] T.W. Haynes, P.J. Slater and S.T. Hedetniemi, Fundamentals of Domination in graphs, Marcel Dekker, New York, (1998). [5] J. John and N. Arianayagam, The detour domination number of a graph, Discrete Mathematics Algorithms and Applications, 09(01), 2017, 17500069. [6] J. John and N. Arianayagam, The total Detour number of a graph, Journal of Discrete Mathematics Sciences and Cryptography, 17(4), 2014, 337-350. [7] J. John and V. R. Sunil Kumar, The open detour number of a graph, Discrete Mathematics Algorithms and Applications, 13(01), 2021, 2050088. [8] A. P. Santhakumaran and S. Athisayanathan, The connected detour number of graphs, J. combin. math. combin. compute;69, (2009), 205-218. [9] J. Vijaya Xavier Parthian, and C. Caroline Selvaraj, Connected Detour Domination Number of Some Standard Graphs, Journal of Applied Science and Computations, 5(11), (2018), 486-489. 212 https://www.researchgate.net/profile/N-Arianayagam?_sg%5B0%5D=AI8km30mFUbw6vP_hPl9FTAsnLnak-i2emHKKKuA4Zw9oC2x4MKObWN8Oj0nLIauNjuBrjI.CbGvUuNINZtp-Y4AjV71IuCMrWfnPmZmURX7jtZ-dQq4Fjb4P4k7GZvko4hMN_BxkxtfM7JaruySm8nQoXbacA&_sg%5B1%5D=DV6mVIhbOCf9VAIH5RrssO-Je9wRghyj5Y-_-Alrb6kxAc5QHxGgEecwfSveUHTNDAuEUNA.xXdOC98Db55iY810UoyM2F2ldXHc9XgoAZclMuJ62k8KsI7zHYaJX2FffIQYLZpQJTkY1x4HbNBeXgwtp14cLw http://dx.doi.org/10.1142/S1793830917500069 https://www.researchgate.net/profile/N-Arianayagam?_sg%5B0%5D=AI8km30mFUbw6vP_hPl9FTAsnLnak-i2emHKKKuA4Zw9oC2x4MKObWN8Oj0nLIauNjuBrjI.CbGvUuNINZtp-Y4AjV71IuCMrWfnPmZmURX7jtZ-dQq4Fjb4P4k7GZvko4hMN_BxkxtfM7JaruySm8nQoXbacA&_sg%5B1%5D=DV6mVIhbOCf9VAIH5RrssO-Je9wRghyj5Y-_-Alrb6kxAc5QHxGgEecwfSveUHTNDAuEUNA.xXdOC98Db55iY810UoyM2F2ldXHc9XgoAZclMuJ62k8KsI7zHYaJX2FffIQYLZpQJTkY1x4HbNBeXgwtp14cLw http://dx.doi.org/10.1142/S1793830917500069