Ratio Mathematica Volume 44, 2022 The Upper and Forcing Fault Tolerant Geodetic Number of a Graph T. Jeba Raj 1 K. Bensiger 2 Abstract A fault tolerant geodetic is said to be minimal fault tolerant geodetic set of if no proper subset of is a fault tolerant geodetic set of is called the upper fault tolerant geodetic number of is denoted by . Some general properties satisfied by this concept are studied. For connected graphs of order with to be is given. It is shown that for every pair of with , there exists a connected graph such that and , where is the fault tolerant geodetic number of and is the upper fault tolerant geodetic number of a graph. Let S be a -set of . A subset is called a forcing subset for if is the unique -set containing T. A forcing subset for of minimum cardinality is a minimum forcing subset of . The forcing fault tolerant geodetic number of S, denoted by , is the cardinality of a minimum forcing subset of . The forcing fault tolerant geodetic number of , denoted by is , where the minimum is taken over all -sets in . The forcing fault tolerant geodetic number of some standard graphs are determined. Some of its general properties are studied. It is shown that for every pair of positive integers and with and there exists a connected graph such that and Keywords: tolerant geodetic, connected graphs, minimum cardinality. 2010 AMS subject classification:05C12, 05C69 3 1 Assistant Professor, Department of Mathematics, Malankara Catholic College, Mariagiri, Kaliyakkavilai - 629 153, India, Email: jebarajmath@gmail.com 2 Register Number. 20123082091004, Research Scholar, Department of Mathematics, Malankara Catholic College, Mariagiri, Kaliyakkavilai - 629 153, India. Email: bensigerkm83@gmail.com (Affiliated to Manonmaniam Sundaranar University, Abishekapatti, Tirunelveli - 627 012, Tamil Nadu, India.) 3 Received on June23rd, 2022. Accepted on Aug 10 th , 2022. Published on Nov30th, 2022.doi: 10.23755/rm.v44i0.903. ISSN: 1592-7415. eISSN: 2282-8214. ©The Authors.This paper is published under the CC-BY license agreement. 167 T. Jeba Raj & K. Bensiger 1. Introduction By a graph we mean a finite, undirected connected graph without loops or multiple edges. The order and size of are denoted by and respectively. For basic graph theoretic terminology, we refer to [9]. Two vertices and of said to be adjacent in if The neighborhood of the vertex in is the set of vertices adjacent to . The degree of the vertex is If is an edge of a graph with and then we call an end edge, a leaf and a support vertex. For any connected graph , a vertex is called a cut vertex of if is disconnected. The subgraph induced by set of vertices of a graph is denoted by with and . A vertex is called an extreme vertex of if is complete. A vertex is an internal vertex of an path if is a vertex of and An edge of is an internal edge of an path if is an edge of with both of its ends or in . The distance between two vertices and in a connected graph is the length of a shortest path in . An path of length is called an geodesic. A vertex is said to lie on an geodesic if isa vertex of including the vertices and . For a vertex of the eccentricity is the distance between and a vertex farthest from . The minimum eccentricity among the vertices of is the radius, and the maximum eccentricity is its diameter, . We denote by and by The closed interval consists of and all vertices lying on some geodesic of . For a non-empty set , the set is the closure of A set is called a geodetic set if Thus every vertex of is contained in a geodesic joining some pair of vertices in . The minimum cardinality of a geodetic set of is called the geodetic number of and is denoted by . A geodetic set of minimum cardinalities is called -set of . For references on geodetic parameters in graphs see [4, 5, 6, 7, 10]. Let be a geodetic set of . be the set of extreme vertices of . Then is said to be a fault tolerant geodetic set of , if is also a geodetic set of for every The minimum cardinality of a fault tolerant geodetic set is called fault tolerant geodetic number and is denoted by . The minimum fault tolerant geodetic dominating set of is denoted by -set of The following theorem is used in the sequel. Theorem 1.1. [6] Each extreme vertex of a connected graph belongs to every geodetic set of G. 168 The upper and Forcing Fault Tolerant Geodetic Number of A Graph 2. The Upper Fault Tolerant Geodetic Number of a Graph Definition 2.1. A fault tolerant geodetic is said to be minimal fault tolerant geodetic set of if no proper subset of is a fault tolerant geodetic set of is called the upper fault tolerant geodetic number of is denoted by Example 2.2. For the graph given in Figure 2.1, is a -setof so that . Let Then is a minimal faulttolerant geodetic set of and so It is easily verified that there is no faulttolerant geodetic set of with cardinality more than six. Therefore . Observation 2.3. (i) For a connected graph of order (ii) No cut vertex of belongs to any minimal fault tolerant geodetic set of . (iii) Each extreme vertex of belong to any minimal fault tolerant geodetic set of G. Theorem 2.4. For the complete graph Proof: This follows from Observation 2.3(iii). ∎ Theorem 2.5. For any non-trivial tree, number of end vertices Proof: This follows from Observation 2.3(ii) and (iii). ∎ Theorem 2.6. For the cycle = Proof: Let n be even. Let be the antipodal vertex of and be the antipodal vertex of , where . Then } is a minimal fault tolerant geodetic set of and so . We prove that = . On the contrary, suppose that . 169 T. Jeba Raj & K. Bensiger Then there exists a geodetic set such that . Then there exist at least two pair of antipodal vertices of G. Hence it follows that , which is a contradiction. Therefore = 4. Let be odd. Let and be two adjacent vertices of . Let and be antipodal vertices of and be two antipodal vertices of . Then is a minimal fault tolerant geodetic set of and so ≥ 5. We prove that = 5. On the contrary, suppose that ≥ 6. Then there exists a fault tolerant geodetic set of such that Then contains two pair of antipodal vertices. Which implies , which is a contradiction. Therefore = 5. ∎ Theorem 2.7. Let G be the complete bipartite graph = Proof: Let and be the two bipartite sets of . Let where is a fault tolerant geodetic set of and so . We prove that = . On the contrary, suppose that ≥ . Then there exists a fault tolerant geodetic set of such that . Which implies , which is a contradiction. Therefore .∎ Theorem 2.8. For every pair of with , there exists a connected graph such that and Proof: Let be a path on five vertices and Let be a graph obtained from and by joining each with and . Let be the graph obtained from by introducing the vertices and join each with . The graph is shown in Figure 2.2. First, we prove that . Let be the set of end vertices of . By Observation 2.3(iii), is a subset of every fault tolerant geodetic set of . It is easily verified that there is no fault tolerant geodetic set of cardinality less than a and so Let is a fault tolerant geodetic set of so that Next, we prove that . Let Then is a minimal fault tolerant geodetic set of and so We prove that On the contrary, suppose that Then there existsa fault tolerant geodetic set of such that Since and it follows that either or , which is a contradiction. Therefore ∎ 170 The upper and Forcing Fault Tolerant Geodetic Number of A Graph 3. The Forcing Fault Tolerant Geodetic Number of a Graph Definition 3.1. Let be a -set of . A subset is called a forcing subset for if is the unique -set containing . A forcing subset for of minimum cardinality is a minimum forcing subset of . The forcing fault tolerant geodetic number of , denoted by is the cardinality of a minimum forcing subset of . The forcing fault tolerant geodetic number of , denoted by , is where the minimum is taken over all - sets in Example 3.2. For the graph given in Figure 3.1, are the only two -sets of so that so that and The next theorem follows immediately from the definition of the forcing fault tolerant geodetic number of the graph. 171 T. Jeba Raj & K. Bensiger Theorem 3.3. For any connected graph In the following we determine the forcing fault tolerant geodetic number of some standard graphs. Theorem 3.4. For a non-trivial tree Proof: Since for a tree , the set of end vertices of is the unique -set of Hence it follows that = 0. ∎ Theorem 3.5. For the complete graph Proof: Since is the unique -set of , ∎ Theorem 3.6. For the cycle = Proof: Let Case 1. Let is even. For , ) is the unique -set of so that = 0. So, let . let Let be a -set of , where is the antipodal vertex of and is the antipodal vertex of . Since , -set of is not unique and so = 1. Since is the unique -set of containing , ( ) = 1 so that = 1. Case 2. Let is odd. For is the unique -set of so that = 0. So, let . let Then it is easily verified that no singleton or two element subsets of a -set is not a forcing subset of . Let = Then is the -set of containing { . Therefore = 3. ∎ Theorem 3.7. For the fan graph = 0. Proof: Let and is the unique -set of so that = 0. ∎ Theorem 3.8. For the wheel graph , = 0. Proof: Let and is the unique -set of so that = 0. ∎ Theorem 3.9. For the complete bipartite graph = Proof: Let } and be the two partite sets of Let . Then By Theorem, = 0. 172 The upper and Forcing Fault Tolerant Geodetic Number of A Graph For and . Then is the unique -set of so that = 0. So let . Then is the unique -set of so that = 0.For , let be a -set of . Then any two element subsets of is a forcing subset of and so ≥ 3. Let . Then { } is a forcing subset of so that = 3. Since this is true for al - set of , = 3. Let and . Let be a -set of . Then one or two or three element subsets of is a forcing subset of and so ≥ 4. Let = { }. Then is a forcing subset of so that = 4. Since this is true for all -set of , = 4. ∎ Theorem 3.10. For every pair of positive integers and with and there exists a connected graph such that = and Proof: Let be a path on three vertices. Let be a copy of path on three vertices. Let be the graph obtained from and by adding new vertices and introducing the edges and . The graph is shown in Figure 3.2. First, we prove that . Let Then is a subset of every -set of . Let Then every -set of contains at least one vertex from each and so ≥ . Let Then is a -set of so that = b. Next, we prove that . By Theorem Now since every is a subset of every -set of and every -set contains at least one vertex from each every -set is of the form where Let be a forcing subset with Then there exists for some such that Therefore ∎ 173 T. Jeba Raj & K. Bensiger References [1] H.A. Ahangar, S. Kosari, S.M. Sheikholeslami and L. Volkmann, Graphs with large geodetic number, Filomat, 29:6 (2015), 1361 – 1368. [2] H. AbdollahzadehAhangar, V. Samodivkin, S. M. Sheikholeslami and Abdollah Khodkar, The restrained geodetic number of a graph, Bulletin of the Malaysian Mathematical Sciences Society, 38(3), (2015), 1143-1155. [3] H. Abdollahzadeh Ahangar, Fujie-Okamoto, F. and Samodivkin, V., On the forcing connected geodetic number and the connected geodetic number of a graph, Ars Combinatoria, 126, (2016), 323-335. [4] H. AbdollahzadehAhangar and Maryam Najimi, Total Restrained Geodetic Number of Graphs, Iranian Journal of Science and Technology, Transactions A: Science, 41, (2017), 473–480. [5] F. Buckley and F. Harary, Distance in Graphs, Addition- Wesley, Redwood City, CA, (1990). [6] G. Chartrand, P. Zhang, The forcing geodetic number of a graph, Discuss. Math. Graph Theory, 19 (1999), 45–58. [7] G. Chartrand, F. Harary and P. Zhang, “On the geodetic number of a graph”, Networks, 39(1), (2002), 1 - 6. [8] H. Escaudro, R. Gera, A. Hansberg, N. Jafari Rad and L. Volkmann,” Geodetic domination in graphs”, Journal of Combinatorial Mathematics and Combinatorial Computing, 77, (2011), 88- 101. [9] T.W. Hayes, P.J. Slater and S.T. Hedetniemi, Fundamentals of domination in graphs, Boca Raton, CA: CRC Press, (1998). [10] A. Hansberg and L. Volkmann, On the geodetic and geodetic domination numbers of a graph, Discrete Mathematics, 310, (2010), 2140-2146. [11] Mitre C. Dourado, Fabio Protti, Dieter Rautenbach and Jayme L. Szwarcfiter, Some remarks on the geodetic number of a graph, Discrete Mathematics,310, (2010), 832-837. [12] H.M. Nuenay and F.P. Jamil,” On minimal geodetic domination in graphs”, Discussiones Mathematicae graph Theory, 35, (3), (2015), 403-418. 174