Skip to main content
Advertisement
Browse Subject Areas
?

Click through the PLOS taxonomy to find articles in your field.

For more information about PLOS Subject Areas, click here.

  • Loading metrics

Fault-tolerant partition resolvability of cycle with chord

Abstract

In the realm of connected networks, distance-based parameters, particularly the partition dimension of graphs, have extensive applications across various fields, including chemistry and computer science. A notable variant of the partition dimension is the fault-tolerant resolving partition, which is critical in computer science for networking, optimization, and navigation tasks. In networking, fault-tolerant partitioning ensures robust communication pathways even in the event of network failures or disruptions. In optimization, it aids in developing efficient algorithms capable of withstanding errors or changes in input data. In navigation systems, fault-tolerant partitioning supports reliable route planning and navigation services under uncertain or dynamic conditions. This paper focuses on the fault-tolerant partition dimension within the specific context of the cycle with chord graphs, exploring its properties and implications for enhancing the robustness and reliability of networked systems.

Introduction

Graph theory is a pivotal field of study with profound implications in today’s digital era. It finds extensive applications in robotics, chemistry, and computer science. In particular, graph theory addresses challenges in computer networks, robot network localization, and the development of various chemical network structures. Applications of cycles with chords are notable in areas such as distributed cycle detection [1] and routing optimization [2]. Additionally, this concept is useful in studying diffusion mechanisms and scheduling aircraft. Understanding how to determine vertex positions in a connected graph using distance parameters is crucial for managing graph-structured networks. One significant parameter in this context is the metric dimension (MD) of a graph, which has proven valuable in many scientific domains. The concept of the metric dimension, defined as the minimal cardinality of a resolving set within a graph, was independently introduced by Slater and Harary et al. [3, 4] and recently generalized in various scenarios; see e.g. [57].

Chartrand et al. [8] introduced the concept of partition dimension (PD) as a standardized alternative to the metric dimension (MD) of a graph. The PD has been calculated for various classes of graphs. For instance, Khabyah et al. determined the PD of nanosheets and nanotubes derived from octagonal grids [9]. Bhatti et al. examined the PD of generalized hexagonal cellular networks and its applications [10]. Chu et al. addressed the PD problem in the context of convex polytopes [11], while Wei et al. explored cycle-related graphs [12].

Garey et al. [13] highlighted that computing the MD for general graphs is an NP-hard problem. Subsequently, Khuller et al. [14] also confirmed the NP-hardness of the MD problem. Given that the PD is a variant of the MD, computing the PD similarly encounters significant computational complexity, thereby establishing it as an NP-hard problem as well.

Javaid et al. [15] introduced and investigated the concept of fault-tolerant partition dimension (FTPD) in graph theory, representing a significant advancement in the study and application of partition dimension (PD). The FTPD enhances the traditional PD by incorporating resilience against faults or errors in the vertex identification process within a graph. This development is particularly relevant to practical scenarios where robustness and reliability are paramount, such as in network design and fault-tolerant systems. Kamran et al. explored the FTPD in various contexts, including mesh networks [16], cycle-related graphs [17], and chemical graphs [18]. Additionally, Nadeem et al. examined the FTPD of Toeplitz networks and the 2-partition dimension of circulant graphs Cn (1, 2, 3, 4) [19, 20]. In this study, we build upon these foundational works by investigating the FTPD specifically within the context of the cycle with chord graphs.

Applications

Metric dimension (MD) finds extensive applications in various fields, including network discovery and verification [21], combinatorial optimization [14], image processing [22], and the modeling of chemical substances. The fault-tolerant partition dimension (FTPD) extends these applications to more specialized areas. It is relevant in routing optimization problems [23], supply chain optimization [24], managing water flow in localities [16], and deploying sensors in residential settings [17].

Preliminaries

Let G be a graph with vertex set VG and edge set EG. For vertices a, bVG, the distance between a and b in G, denoted by d(a, b), is the length of the shortest path connecting them. If LVG, the distance from a to L, denoted by d(a, L), is defined as d(a, L) = min{d(a, x) ∣ xL}.

For a vertex aVG, the open neighborhood N(a) consists of all vertices adjacent to a, that is, N(a) = {bVGa is adjacent to b}. The closed neighborhood N[a] includes the open neighborhood along with a itself, i.e., N[a] = N(a) ∪ {a} (see [25]).

Given a set Ω = {ai ∣ 1 ≤ ik} ⊂ VG, the representation of vertex a with respect to Ω, denoted by r(a∣Ω), is the k-dimensional vector , where each component represents the distance from a to the vertex ai in Ω.

Consider G to be a connected graph with vertex set V(G), which can be partitioned into a partition set Ψ. An ordered q-partition Ψ is called a resolving partition if the representations of all vertices are unique. The smallest integer q for which such a partition exists is known as the partition dimension (PD) of the graph.

The concept of partition dimension has been advanced to the fault-tolerant partition dimension (FTPD) of a graph. For an ordered q-partition Ψ to be considered a fault-tolerant resolving partition, it must ensure that the representations of each pair of distinct vertices in G are distinct in at least two positions. The smallest integer q for which such a partition exists is referred to as the fault-tolerant partition dimension of the graph, denoted by .

Important results of FTPD

Below are some notable results concerning the fault-tolerant partition dimension (FTPD) of a connected graph G with n ≥ 2 vertices.

Proposition 0.1 [26] , where, n ≥ 3.

Proposition 0.2 [25] , where, n ≥ 3.

Proposition 0.3 [26] if and only if GKn or GKne, where Kn is a complete graph.

In the remaining part of the article, the FTPD of cycle with chord section is dedicated to computing , where denotes a cycle with chord graph. The paper concludes in the Conclusion section with the proposal of an open problem.

FTPD of cycle with chord

This part is devoted to the calculation of FTPD of the cycle with chord. The graph is a cycle with a chord, where two vertices at a distance t in the cycle Cn are connected by an edge. The and are vertex set and edge set respectively. Clearly, is same as for n ≥ 4, and 2 ≤ tn − 2. Therefore, it is enough to compute , for n ≥ 4 and . Graph of cycle with chord is shown in Fig 1.

Lemma 0.4 [27] For n ≥ 4 and , MD of .

Lemma 0.5 [12] For n ≥ 4 and , PD of .

Following is the main result of the paper which computes the FT partition dimension of .

Theorem 0.6 For n ≥ 4 and , .

Proof. To demonstrate that , we first establish . In this context, consider Ψ = {Ψ1, Ψ2, Ψ3, Ψ4} be a partition of , next, we examine the following cases:

  1. Case (i) For 4 ≤ n ≤ 5.
    It is evident that Ψ forms FT resolving partition of , with Ψ1 = {v1}, Ψ2 = {v2}, Ψ3 = {v3} and Ψ4 = {vq : 4 ≤ qn}.
  2. Case (ii) For n ≥ 6, we have the following subcases:
  3. Subcase ii(a) If n = 2ζ and 2 ≤ tζ − 1, then representation of vertices (Rv) with regard to Ψ1 = {vq : 1 ≤ qζ}, Ψ2 = {vζ+1}, Ψ3 = {vq : ζ + 2 ≤ qζ + t} and Ψ4 = {vq : ζ + t + 1 ≤ qn} can be seen in Tables 16.
  4. Subcase ii(b) If n = 2ζ and t = ζ, then Rv with regard to Ψ1 = {vq : 1 ≤ qζ − 1}, Ψ2 = {vζ}, Ψ3 = {vq : ζ + 1 ≤ qn − 1} and Ψ4 = {vn} can be seen in Tables 7 and 8.
  5. Subcase ii(c) If n = 2ζ + 1 and 2 ≤ tζ − 1, then Rv with regard to Ψ1 = {vq : 1 ≤ qζ}, Ψ2 = {vζ+1}, Ψ3 = {vq : ζ + 2 ≤ qζ + t + 1} and Ψ4 = {vq : ζ + t + 2 ≤ qn} can be seen in Tables 914.
  6. Subcase ii(d) If n = 2ζ + 1 and t = ζ, then Rv with regard to Ψ1 = {vq : 1 ≤ qζ + 1}, Ψ2 = {vζ+2}, Ψ3 = {vq : ζ + 3 ≤ qn − 1} and Ψ4 = {vn} can be seen in Tables 15 and 16.
    It is clear from Cases (i)-(ii), that Ψ is FT resolving partition of , therefore, .
thumbnail
Table 2. Rv for n = 2ζ and t = 2ϖ − 1.

For 8 ≤ n ≤ 36, and for n ≥ 38, .

https://doi.org/10.1371/journal.pone.0313300.t002

thumbnail
Table 3. Rv for n = 2ζ and t = 2ϖ − 1.

For 16 ≤ n ≤ 36, and for n ≥ 38, .

https://doi.org/10.1371/journal.pone.0313300.t003

thumbnail
Table 5. Rv for n = 2ζ and t = 2ϖ.

For 10 ≤ n ≤ 24, and for n ≥ 26, .

https://doi.org/10.1371/journal.pone.0313300.t005

thumbnail
Table 6. Rv for n = 2ζ and t = 2ϖ.

For 18 ≤ n ≤ 24, , and for n ≥ 26, .

https://doi.org/10.1371/journal.pone.0313300.t006

thumbnail
Table 10. Rv for n = 2ζ + 1 and t = 2ϖ.

For 7 ≤ n ≤ 21, and for n ≥ 23, .

https://doi.org/10.1371/journal.pone.0313300.t010

thumbnail
Table 11. Rv for n = 2ζ + 1 and t = 2ϖ.

For 15 ≤ n ≤ 21, and for n ≥ 23, .

https://doi.org/10.1371/journal.pone.0313300.t011

thumbnail
Table 13. Rv for n = 2ζ + 1 and t = 2ϖ − 1.

For 9 ≤ n ≤ 33, and for n ≥ 35, .

https://doi.org/10.1371/journal.pone.0313300.t013

thumbnail
Table 14. Rv for n = 2ζ + 1 and t = 2ϖ − 1.

For 17 ≤ n ≤ 33, and for n ≥ 35, .

https://doi.org/10.1371/journal.pone.0313300.t014

Now, we establish that . To do this, we demonstrate that . Suppose to the contrary that . Let Ψ = {Ψ1, Ψ2, Ψ3} be a FT resolving partition of . Let vi ∈ Ψ1 and N(vi) = {u1, u2, u3}, where u3 is also a vertex of degree 3. Suppose that |Ψ1| = 1, and N(vi) ⊆ Ψ2 ∪ Ψ3, by Pigeonhole principle |N(vi) ∩ Ψ2| ≥ 2 or |N(vi) ∩ Ψ3| ≥ 2. Without loss of generality, we assume that at least two vertices a, bN(vi) ∩ Ψ2. Since, r(a|Ψ) = (1, 0, c1) and r(b|Ψ) = (1, 0, c2) show equal distances at two positions, resulting in a contradiction.

Now considering that |Ψ1| ≥ 2 and vi ∈ Ψ1, we encounter the following scenarios:

  1. Case 1: If each of the three vertices u1, u2, u3 ∈ Ψ1, then r(vi|Ψ) = (0, p0, q0), r(u1|Ψ) = (0, p1, q1), r(u2|Ψ) = (0, p2, q2) and r(u3|Ψ) = (0, p3, q3). As p0 − 1 ≤ p1, p2, p3p0 + 1, thus, two vertices having the same distance at two locations lead to a contradiction.
  2. Case 2: If r(vi|Ψ) = (0, 1, q0), and two vertices u1, u2 ∈ Ψ1 and another vertex u3 ∈ Ψ2, then, r(u1|Ψ) = (0, p1, q1), r(u2|Ψ) = (0, p2, q2) and r(u3|Ψ) = (1, 0, q3). Since 1 ≤ u1, u2 ≤ 2, two vertices will again have the same distance at two positions, resulting in a contradiction.
  3. Case 3: If one vertex say, u1 ∈ Ψ1, and two vertices u2, u3 ∈ Ψ2, then r(vi|Ψ) = (0, 1, q0), r(u1|Ψ) = (0, p1, q1), r(u2|Ψ) = (1, 0, q2) and r(u3|Ψ) = (1, 0, q3). Again r(u2|Ψ) and r(u3|Ψ) are the same at two positions, resulting in a contradiction.
  4. Case 4: If N(vi) ∩ Ψ1 = ∅, all the three vertices u1, u2, u3 ∈ Ψ2, then r(vi|Ψ) = (0, 1, q0), r(u1|Ψ) = (1, 0, q1), r(u2|Ψ) = (1, 0, q2), r(u3|Ψ) = (1, 0, q3). Again r(u1|Ψ), r(u2|Ψ) and r(u3|Ψ) are the same at two positions, resulting in a contradiction.
  5. Case 5: If N(vi) ∩ Ψ1 = ∅, two vertices u1, u2 ∈ Ψ2, and one vertex u3 ∈ Ψ3, then r(vi|Ψ) = (0, 1, q0), r(u1|Ψ) = (1, 0, q1), r(u2|Ψ) = (1, 0, q2). Again r(u1|Ψ) and r(u2|Ψ) are the same at two positions, resulting in a contradiction.
  6. Case 6: If one vertex say, u1 ∈ Ψ1, u2 ∈ Ψ2 and u3 ∈ Ψ3, then r(vi|Ψ) = (0, 1, 1). We have the following subcases:
    1. Case 6(a) If t = 2, then r(u1|Ψ) = (0, 2, 1), resulting in a contradiction.
    2. Case 6(b) If t = 3, then consider N(u1) = {w1, vi}, N(u2) = {w2, vi} and N(u3) = {w3, vi}. Let w1 ∈ Ψ1 and w2, w3 ∈ Ψ2 ∪ Ψ3. We can assume without loss of generality that w2, w3 ∈ Ψ2, then r(u2|Ψ) = (1, 0, 2), r(w2|Ψ) = (2, 0, c1) and r(w3|Ψ) = (2, 0, 1). The representation of two vertices being identical at two positions leads to a contradiction. If w3 ∈ Ψ2 and w2 ∈ Ψ3, then, r(u2|Ψ) = (1, 0, 1) and r(w3|Ψ) = (2, 0, 1), results to a contradiction. Now if w2 ∈ Ψ2 and w3 ∈ Ψ3, then, r(u1|Ψ) = (0, 2, 2) and r(w1|Ψ) = (0, c2, 1). As r(vi|Ψ) and r(w1|Ψ) are identical at two positions which is again a contradiction.
    3. Case 6(c) For , consider N(u1) = {w1, vi}, N(u2) = {w2, vi} and . Let w1 ∈ Ψ1 and . We can assume without loss of generality that belong to Ψ2, so, r(u2|Ψ) = (1, 0, d1), r(w2|Ψ) = (2, 0, d2) and r(w3|Ψ) = (2, 0, 1). Since the representation of w2 and w3 at two positions are identical, thus a contradiction. Now if and w2 ∈ Ψ3, r(u2|Ψ) = (1, 0, 1) and r(w3|Ψ) = (2, 0, 1). Since the representation of two vertices is identical at two positions, this leads to a contradiction. If w2 ∈ Ψ2 and , then, r(u3|Ψ) = (1, 2, 0), r(w3|Ψ) = (2, f1, 0) and . Two vertices have the same distance at two positions, resulting in a contradiction.

Based on all the aforementioned cases, it is evident that , thereby concluding the proof.

Conclusion

In this paper, we have demonstrated that the fault-tolerant partition dimension (FTPD) of a cycle with chord graph is for n ≥ 4 and . This result indicates that the FTPD of these graphs is constant, specifically 4, regardless of the values of n and t within the specified ranges. Our findings contribute to a deeper understanding of the FTPD in the context of the cycle with chord graphs, providing a clear and consistent value for this parameter across various graph sizes and chord configurations.

Despite this advancement, several questions remain unresolved in the field. One particularly intriguing open problem is to determine whether similar constant values can be established for the FTPD of other classes of graphs or under different graph parameters. Further exploration is needed to generalize the results and understand the implications of FTPD in broader contexts. We encourage future research to investigate these aspects and explore potential applications of these findings in network design, optimization, and fault tolerance. Moreover, we propose the following open problem.

Open Problem 0.7 Compute FTPD of multilevel-cycles with chord.

Open Problem 0.8 Compute fault tolerant metric dimension of the cycle with chord.

Acknowledgments

The authors would like to thank all reviewers and the editor-in-chief for their insightful comments that have improved the quality of the final manuscript.

References

  1. 1. Boukerche A, Tropper C. A distributed algorithm for the detection of local cycles and knots. Proceedings of 9th International Parallel Processing Symposium Santa Barbara, CA, USA, 1995;118–127.
  2. 2. Jafari1 H, Bakhsheshi E, Derakhshi ARF. Presenting a mathematical programming model for discovering Eulerian paths in certain specific graphs. Int. J. Innov. Eng. 2023;3(2):1–7.
  3. 3. Harary F, Melter RA. On the metric dimension of a graph. Ars Combin. 1976;2:191–195.
  4. 4. Slater PJ. Leaves of trees. Proc. 6th Southeastern Conf. Combinatorics, Graph Theory, and Computing. Congr. Numer. 1975;14:549–559.
  5. 5. Ali I, Javaid M, Shang Y. Computing dominant metric dimensions of certain connected networks. Heliyon 2024;10(4):e25654. pmid:38370250
  6. 6. Azeem M, Jamil MK, Shang Y. Notes on the localization of generalized hexagonal cellular networks Mathematics 2023;11(4):844.
  7. 7. Saha L, Lama R, Tiwary K, Das KC, Shang Y. Fault-tolerant metric dimension of circulant graphs. Mathematics 2022;10(1):124.
  8. 8. Chartrand G, Salehi E, Zhang P. The partition dimension of a graph. Aequ. Math. 2000;59:45–54.
  9. 9. Khabyah AA, Koam ANA, Ahmad A. Partition resolvability of nanosheet and nanotube derived from octagonal grid. J. Math. 2024;2024:6222086.
  10. 10. Bhatti R, Jamil MK, Azeem M, Poojary P. Partition dimension of generalized hexagonal cellular networks and its application. IEEE Access 2024;12:12199–12208.
  11. 11. Chu YM, Nadeem MF, Azeem M, Siddiqui MK. On sharp bounds on partition dimension of convex polytopes. IEEE Access 2020;8:224781–224790.
  12. 12. Wei C, Nadeem MF, Siddiqui HMA, Azeem M, Liu JB, Khalil A. On partition dimension of some cycle-related graphs. Math. Probl. Eng. 2021;2021:4046909.
  13. 13. Garey MR, Johnson DS. Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, New York, 1979.
  14. 14. Khuller S, Raghavachari B, Rosenfeld A. Landmarks in graphs. Discret. Appl. Math. 1996;70:217–229.
  15. 15. Javaid I, Salman M, Chaudhry MA, Shokat S. Fault-tolerance in resolvability. Utilitas Math. 2009;80:263–275.
  16. 16. Azhar K, Zafar S, Kashif A, Aljaedi A, Albalawi U. Fault-tolerant partition resolvability in mesh related networks and applications. IEEE Access 2022;10:71521–71529.
  17. 17. Azhar K, Zafar S, Kashif A, Aljaedi A, Albalawi U. The application of fault-tolerant partition resolvability in cycle related graphs. Appl. Sci. 2022;12:9558.
  18. 18. Azhar K, Zafar S, Kashif A, Zahid Z. Fault-tolerant partition resolvability in chemical graphs. Polycycl. Aromat. Comp. 2023;43:8830–8840.
  19. 19. Nadeem A, Kashif A, Aljaedi A, Zafar S. On the fault tolerant partition resolvability of toeplitz networks. Math. Probl. Eng. 2022;2022:3429091.
  20. 20. Nadeem A, Azhar K, Kashif A, Zafar S, Zahid Z. On the partition dimension of the circulant graph Cn(1, 2, 3, 4). Punjab Univ. J. Math. 2023;55(3):117–133.
  21. 21. Beerliova Z, Eberhard F, Erlebach T, Hall A, Hoffmann M, Mihalák M, Ram LS. Network discovery and verification. IEEE J. Sel. Areas Commun. 2006;24(12):2168–2181.
  22. 22. Melter RA, Tomescu I. Metric bases in digital geometry. Computer Vision Graphics and Image Processing 1984;25(1):113–121.
  23. 23. Azhar K, Zafar S, Kashif A. On fault-tolerant partition dimension of homogeneous caterpillar graphs. Math. Probl. Eng. 2021;2021:7282245.
  24. 24. Azhar K, Zafar S, Kashif A, Zahid A. On fault-tolerant partition dimension of graphs. J. Intell. Fuzzy Syst. 2020;4(1):1129–1135.
  25. 25. Moreno AE. On the k−partition dimension of graphs. Theor. Comput. Sci. 2020;806:42–52.
  26. 26. Salman M, Javaid I, Chaudhry M. Fault-tolerant metric and partition dimension of graphs. Utilitas Math. 2010;83:187–199.
  27. 27. Ahmad A, Bača M, Sultan S. Computing the metric dimension of kayak paddles graph and cycles with chord. Proyecciones 2020;39(2):287–300.