Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 7s (2025) 688 https://internationalpubls.com Fault-Tolerant Strong Metric Dimension of Rooted Product Graphs H. Prathab1,2, S. Chandrasekaran3 and Sathish Krishnan4* 1Department of Mathematics, Saveetha Engineering College, Chennai, 602105, India. 2Research Scholar, P.G & Research Department of Mathematics Pachaiyappa’s College, Chennai, 600030, India. 3P.G & Research Department of Mathematics, Pachaiyappa’s College, Chennai, 600030, India. 4*Department of Mathematics and Statistics, Faculty of Science and Humanities SRM Institute of Science and Technology, Chengalpattu, 603203, India. *Corresponding Author. e-mail: satiskris@gmail.com sathishk6@srmist.edu.in Article History: Received: 27-10-2024 Revised:11-11-2024 Accepted:19-12-2024 Abstract: The concept of fault tolerance in graph theory is critical in designing robust networks, ensuring that essential graph properties are preserved despite failures of vertices or edges. In this paper, we investigate the fault-tolerant strong metric dimension of rooted product graphs, a class of graphs derived by attaching multiple copies of a rooted graph to each vertex of a base graph. We extend the notion of a strong metric dimension by considering scenarios where the strong resolving set remains effective even after a specific number of vertices have failed. We provide exact values for specific families of rooted product graphs and demonstrate how the fault-tolerant property varies with the structure of the root and base graphs. Keywords: Metric dimension, strong metric dimension, fault-tolerant strong metric dimension, rooted product graphs 1. Introduction The study of graph invariants has long been central to graph theory, offering a framework for understanding the structural and combinatorial properties of networks. Among these invariants, the metric dimension and its variants play a pivotal role in problems related to network navigation, resource allocation, and information retrieval. The metric dimension of a graph quantifies the minimum number of vertices required to uniquely determine the position of any other vertex within the graph using distances. The strong metric dimension strengthens the classical concept of metric dimension by imposing stricter conditions on resolving sets, making it particularly useful in applications where precise and robust vertex identification is essential. In modern applications, networks are often subject to failures or disruptions, making fault tolerance a crucial consideration. The fault-tolerant strong metric dimension addresses this challenge by identifying resolving sets that retain functionality even when certain vertices or edges fail. This concept is particularly significant in the design of resilient communication and transportation networks, where the ability to maintain operability under adverse conditions is essential. mailto:satiskris@gmail.com mailto:sathishk6@srmist.edu.in Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 7s (2025) 689 https://internationalpubls.com Rooted product graphs, a construction obtained by combining a base graph with multiple rooted subgraphs, offer a versatile model for various real-world systems. Their hierarchical structure and inherent modularity make them a natural candidate for studying fault-tolerant properties. Despite their relevance, the fault-tolerant strong metric dimension of rooted product graphs remains underexplored in the literature. In this paper, we investigate the fault-tolerant strong metric dimension of rooted product graphs. The results presented here contribute to the theoretical understanding of fault-tolerant graph properties. We exclude the definitions of conventional graph-theoretical concepts. These can be read in [1] and other textbooks. The metric dimension of a graph G = (V, E) is the minimum number of vertices in a subset R  V such that every pair of distinct vertices in G is uniquely identified by their distances to the vertices in R. A set R with this property is called a resolving set, as it enables a unique identification of vertices based on their distance vectors relative to the elements of R. The concept of metric dimension was first studied by Slater [13] (independently by Harary and Melter [3]). Another invariant, more restricted than the metric dimension was presented by Sebö and Tannier in [11], and studied further in several articles [4, 5, 7, 8, 9, 10, 14]. A vertex s  S is said to strongly resolve x and y if d(x, s) = d(x, y) + d(y, s) or d(y, s) = d(y, x) + d(x, s), where d(x, y) denotes a shortest path distance between vertices x and y in G. The strong metric dimension of a graph G = (V, E) is the minimum cardinality of a subset S  V such that for every pair of distinct vertices x, y  V, there exists a vertex s  S that strongly resolves x and y. A fault-tolerant strong resolving set S for a graph G is a set such that for every vertex s  S, the set S \ {s} remains a strong resolving set for G. The fault-tolerant strong metric dimension of G, denoted dimfs(G), is the smallest cardinality of a fault-tolerant strong resolving set for G [6]. A vertex u of G is said to be maximally distant from v if for every w  N(u), d(v, w)  d(v, u). If u is maximally distant from v and v is maximally distant from u, then u and v are said to be mutually maximally distant. The following Lemma and Theorem mentioned in [6] is useful in the sequel. Lemma 1: [6] Let G be a simple connected graph and let S be a fault-tolerant strong resolving set of G. Let u, v  V be mutually maximally distant in G. Then both u and v  S. Theorem 1: [6] A strong resolving set S of a graph G is a fault-tolerant strong resolving set if and only if every pair of vertices in G is strongly resolved by at least two vertices of S. 2. Main results A graph in which one vertex is fixed as a root vertex to distinguish it from other vertices is called a rooted graph. Let G be a graph with n vertices and H be a sequence of n rooted graphs H1, H2 … Hn. The rooted product graph G(H) is obtained from the graphs G, H1, H2 … Hn by identifying the root vertex of Hi with the ith vertex of G [2]. Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 7s (2025) 690 https://internationalpubls.com If H consists of n isomorphic rooted graphs H1  H2  …  Hn, then a particular kind of rooted product graph is generated from G and H, where H  Hi for all i  n. Such a graph is denoted by 𝐺𝜊𝑣𝐻, where v is the root vertex of H [12]. For V(G) = {u1, u2 … un}, the vertex set V and edge set E of the rooted product graph 𝐺𝜊𝑣𝐻 is defined as V = V(G)  V(H) and 𝐸 = ⋃ {(𝑢𝑖, 𝑏)(𝑢𝑖, 𝑦) ∶ 𝑏𝑦 ∈ 𝐸(𝐻)} ∪ {(𝑢𝑖, 𝑣)(𝑢𝑗, 𝑣) ∶ 𝑢𝑖𝑢𝑗 ∈ 𝐸(𝐺)}𝑛 𝑖=1 . We start by stating the following easily verified theorem. Theorem 2: Let G and H be two graphs of order n1 and n2 respectively. Then no two vertices of G are mutually maximally distant in 𝐺𝜊𝑣𝐻. Proof. Assume the contrary. Suppose that there exist two vertices (𝑢𝑖 , 𝑣), (𝑢𝑗, 𝑣), 𝑖 ≠ 𝑗, 1 ≤ 𝑖, 𝑗 ≤ 𝑛1 which are mutually maximally distant in 𝐺𝜊𝑣𝐻. Then for every (𝑢𝑘, 𝑣) ∈ 𝑁 ((𝑢𝑗, 𝑣)), 𝑑((𝑢𝑖, 𝑣), (𝑢𝑘, 𝑣)) ≤ 𝑑 ((𝑢𝑖, 𝑣), (𝑢𝑗, 𝑣)). Let 𝑑 ((𝑢𝑖, 𝑣), (𝑢𝑗, 𝑣)) = 𝑙. Since (𝑢𝑗, 𝑣), (𝑢𝑗, 𝑤) ∈ 𝐸(𝐺𝜊𝑣𝐻) for some 𝑣𝑤 ∈ 𝐸(𝐻𝑗) in 𝐺𝜊𝑣𝐻, 𝑑 ((𝑢𝑖, 𝑣), (𝑢𝑗, 𝑤)) = 𝑑 ((𝑢𝑖, 𝑣), (𝑢𝑗, 𝑣)) + 1 = 𝑙 + 1, which contradicts the fact that 𝑑((𝑢𝑖, 𝑣), (𝑢𝑘, 𝑣)) ≤ 𝑑 ((𝑢𝑖, 𝑣), (𝑢𝑗, 𝑣)). Hence vertices (𝑢𝑖, 𝑣) and (𝑢𝑗, 𝑣) are not mutually maximally distant. By Theorem 2, the following results are obvious. Lemma 2: Let G be a connected graph of order n  2 and H be a connected graph. Let M be the set of all mutually maximally distant vertices in H. Then 1. If v  M, then 𝑑𝑖𝑚𝑓𝑠(G𝜊𝑣H) = 𝑛|𝑀\{𝑣}|. 2. If v  M, then 𝑑𝑖𝑚𝑓𝑠(𝐺𝜊𝑣H) = 𝑛|𝑀|. Figure 1 (a) Graph G (b) P3 (c) G𝜊𝑣𝑃3 where 𝑣 has degree 1. Consider the rooted product graph 𝐺𝜊𝑣𝑃𝑚, where m  2. The degree of root vertex v of Pm, can be either 1 or 2. Depending on the degree of root vertex in Pm, the different classes of graphs can be generated. If the degree of the root vertex v is 1, then the vertices of ith copy of Pm are labelled as (ui, j), 1  j  m – 1 in 𝐺𝜊𝑣𝑃𝑚, except (ui, v). See Figure 1. If the degree of the root vertex v is 2, then the ith copy of Pm will have two distinct paths (ui, 1), (ui, 2) … (ui, a)  Pa and (wi, 1), (wi, 2) … (wi, b)  Pb in 𝐺𝜊𝑣𝑃𝑚 such that a + b + 1 = m. See Figure 2. u1 u2 u3u4 v 1 2 (u1, v) (u2, v) (u2, 1) (u2, 2) (u1, 1) (u1, 2) (u3, v) (u3, 1) (u3, 2) (u4, v) (u4, 1) (u4, 2) (a) (b) (c) Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 7s (2025) 691 https://internationalpubls.com Theorem 3: Let G be a connected graph of order n  2. For m  2, 𝑑𝑖𝑚𝑓𝑠(G𝜊𝑣𝑃𝑚) = { 𝑛 , 𝑑𝑒𝑔(𝑣) = 1; 2𝑛, 𝑑𝑒𝑔(𝑣) = 2. Proof. We have two cases. Case 1: 𝑑𝑒𝑔(𝑣) = 1. Let (ui, m – 1), 1  i  n be the pendant vertices of G𝜊𝑣𝑃𝑚. Clearly the pendant vertices (ui, m – 1) are pairwise mutually maximally distant. Hence by Lemma 1, any fault- tolerant strong resolving set of G𝜊𝑣𝑃𝑚 contains the pendant vertices. Define W = {(ui, m – 1) : 1  i  n }. Figure 2 (a) Graph G (b) P3 (c) G𝜊𝑣𝑃3 where 𝑣 has degree 2. On the other hand, let 𝑊 = {(𝑢𝑖, 𝑚 − 1): 1 ≤ 𝑖 ≤ 𝑛} and let (𝑢𝑖, 𝑘1), (𝑢𝑗, 𝑘2) ∈ 𝑉\𝑊. Clearly the vertices (𝑢𝑖, 𝑘1) and (𝑢𝑗, 𝑘2) are strongly resolved by both (𝑢𝑖, 𝑚 − 1) and (𝑢𝑗, 𝑚 − 1); the shortest path from (𝑢𝑖, 𝑘1) to (𝑢𝑗, 𝑚 − 1) contains (𝑢𝑗, 𝑘2) and similarly the shortest path from (𝑢𝑗, 𝑘2) to (𝑢𝑖, 𝑚 − 1) contains (𝑢𝑖, 𝑘1). Hence by Theorem 2, 𝑊 is a fault-tolerant strong resolving set. Case 2: 𝑑𝑒𝑔(𝑣) = 2. Let (𝑢𝑖, 𝑎) and (𝑤𝑖 , 𝑏), 1 ≤ 𝑖 ≤ 𝑛, be the pendant vertices of G𝜊𝑣𝑃𝑚. Clearly the pendant vertices (𝑢𝑖, 𝑎) and (𝑤𝑖, 𝑏) are pairwise mutually maximally distant. Hence by Lemma 1, any fault-tolerant strong resolving set of G𝜊𝑣𝑃𝑚 contains the pendant vertices. Define 𝑊 = {(𝑢𝑖 , 𝑎), (𝑤𝑖, 𝑏) ∶ 1 ≤ 𝑖 ≤ 𝑛}. On the other hand, let 𝑊 = {(𝑢𝑖, 𝑎), (𝑤𝑖 , 𝑏) ∶ 1 ≤ 𝑖 ≤ 𝑛} and let (𝑢𝑖 , 𝑘1),(𝑢𝑗, 𝑘2) ∈ 𝑉\𝑊. Clearly the vertices (𝑢𝑖, 𝑘1) and (𝑢𝑗, 𝑘2) are strongly resolved by both (𝑢𝑖, 𝑎), (𝑤𝑖 , 𝑏) and (𝑢𝑗, 𝑎), (𝑤𝑗 , 𝑏). Hence by Theorem 2, 𝑊 is a fault- tolerant strong resolving set. Figure 3 (a) Graph G (b) C3 (c) 𝐺𝜊𝑣𝐶3 where v has degree 2. u1 u2 u3u4 v 1 1 (u1, 1) (u2, 1) (u2, v) (w2, 1) (u1, v) (w1, 1) (u3, 1) (u3, v) (w3, 1) (a) (b) (c) (u4, 1) (u4, v) (w4, 1) u1 u2 u3u4 (a) (b) (c) v 2 1 (u1, v) (u2, v) (u2, 1)(u2, 2)(u1, 1)(u1, 2) (u3, v) (u3, 1)(u3, 2) (u4, v) (u4, 1)(u4, 2) Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 7s (2025) 692 https://internationalpubls.com Consider the rooted graph G𝜊𝑣𝐶𝑚, where 𝑚 ≥ 3. Clearly the degree of root vertex 𝑣 is 2 and the vertices of ith copy of Cm are labelled as (𝑢𝑖, 𝑗), 1 ≤ 𝑖 ≤ 𝑚 − 1 in G𝜊𝑣𝐶𝑚 except (𝑢𝑖 , 𝑣). See Figure 3. Theorem 4: Let G be a connected graph of order n  2. For m  2, 𝑑𝑖𝑚𝑓𝑠(G𝜊𝑣𝐶𝑚) = 𝑛(𝑚 − 1). Proof. Let (𝑢𝑖, 𝑣), (𝑢𝑖, 1), (𝑢𝑖 , 2) … (𝑢𝑖, 𝑚 − 1) be the vertices of ith copy of Cm in G𝜊𝑣𝐶𝑚. If m is even, then there is exactly one antipodal vertex (𝑢𝑖, 𝑘∗) from (𝑢𝑖, 𝑘), 1 ≤ 𝑖 ≤ 𝑛, 1 ≤ 𝑘 ≤ 𝑚 − 1. Hence the vertices (𝑢𝑖, 𝑘), 1 ≤ 𝑘 ≤ 𝑚 − 1, must belong to any fault-tolerant strong resolving set W. If m is odd, then there are exactly two antipodal vertices, say (𝑢𝑖, 𝑘1 ∗) and (𝑢𝑖, 𝑘2 ∗) from (𝑢𝑖, 𝑘), 1 ≤ 𝑖 ≤ 𝑛, 1 ≤ 𝑘 ≤ 𝑚 − 1. Hence the vertices (𝑢𝑖, 𝑘), 1 ≤ 𝑘 ≤ 𝑚 − 1, must belong to any fault-tolerant strong resolving set W. Since this is true for every 𝑖, 1 ≤ 𝑖 ≤ 𝑛, |𝑊| = 𝑛(𝑚 − 1). Similarly, we have the following results. Theorem 5: Let G be a connected graph of order n  2. For m  3, 𝑑𝑖𝑚𝑓𝑠(G𝜊𝑣𝐾𝑚) = 𝑛(𝑚 − 1). Theorem 6: Let G be a connected graph of order n  2 and T be a tree. Then 𝑑𝑖𝑚𝑓𝑠(G𝜊𝑣𝑇) equals the number of leaves in G𝜊𝑣𝑇. A wheel graph W1,m, m  3, can also be seen as the graph obtained by adding a single vertex (the hub) to a cycle Cm where the hub is connected to all vertices in Cn. Theorem 7: Let G be a connected graph of order n  2. For m  3, 𝑑𝑖𝑚𝑓𝑠(G𝜊𝑣𝑊𝑚) = { 𝑚𝑛 − 1, 𝑑𝑒𝑔(𝑣) = 𝑚; 𝑛, 𝑑𝑒𝑔(𝑣) = 𝑚 − 1. 3. Conclusion In this paper, we have explored the fault-tolerant strong metric dimension of rooted product graphs, extending the concept of strong metric dimension to account for vertex. We have computed exact values for several families of rooted product graphs, highlighting how the fault-tolerant property depends on the structural characteristics of both the root and base graphs. Future work may involve exploring fault-tolerance in other graph products or generalizing these results to other graph families, with potential applications in areas such as distributed computing, network topology, and communication systems. References [1] J. A. Bondy and U. S. R. Murty, Graph theory with applications, MacMillan, New York, 1976. [2] C. D. Godsil and B. D. McKay, A new graph product and its spectrum, Bull. Aust. Math. Soc. 18 (1978) 21-28. [3] F. Harary and R. A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976) 191-195. [4] J. Kratica, V. Kovačević-Vujčić, M. Čangalović, and M. Stojanović, Minimal doubly resolving sets and the strong metric dimension of some convex polytopes, Appl. Math. Comput. 218(19) (2012) 9790-9801. [5] S. Krishnan, B. Rajan and M. Imran, On the strong metric dimension of certain nanostructures, J. Comput. Theor. Nanosci. 14(1) (2017) 354-358. [6] S. Krishnan and B. Rajan, Fault-tolerant strong metric dimension of graphs, Discrete Mathematics,Algorithms and Applications, 15(7) (2023), 2250162. Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 32 No. 7s (2025) 693 https://internationalpubls.com [7] D. Kuziak, I. G. Yero and J. A. Rodríguez-Velázquez, On the strong metric dimension of corona product graphs and join graphs, Discret. Appl. Math. 161(7-8) (2013) 1022-1027. [8] O. R. Oellermann and J. Peters-Fransen, The strong metric dimension of graphs and digraphs, Discret. Appl. Math. 155(3) (2007) 356-364. [9] K. Sathish and B. Rajan, On strong metric dimension of certain triangular tessellations, Int. J. Pure Appl. Math. 101(5) (2015) 637-645. [10] K. Sathish and H. Prathab, On strong metric dimension of certain interconnection networks, AIP Conference Proceeding, 2852(1) (2023) 020009. [11] A. Sebö and E. Tannier, On metric generators of graphs, Math. Oper. Res. 29(2) (2004) 383-393. [12] A. J. Schwenk, Computing the characteristic polynomial of a graph, Graphs and Combinatorics: Proceedings of the Capital Conference on Graph Theory and Combinatorics at the George Washington University June 18-22, 1973. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006. [13] P. J. Slater, Leaves of trees, Proceeding of the 6th Southeastern Conference on Combinatorics, Graph Theory, and Computing, Congressus Numerantium 14 (1975) 549-559. [14] E. Yi, On strong metric dimension of graphs and their complements, Acta. Math. Sin. English Ser. 29(8) (2013) 1479-1492.