Open Access

ARTICLE

# Minimal Doubly Resolving Sets of Certain Families of Toeplitz Graph

1 Department of Mathematics, University of Management and Technology, Lahore, 54770, Pakistan

2 Department of Mathematics, Cankaya University, Etimesgut, Ankara, 06790, Turkey

3 Department of Medical Research, China Medical University Hospital, China Medical University, Taichung, 40402, Taiwan

* Corresponding Author: Fahd Jarad. Email:

(This article belongs to the Special Issue: Resolvability Parameters and their Applications)

*Computer Modeling in Engineering & Sciences* **2023**, *135*(3), 2681-2696. https://doi.org/10.32604/cmes.2023.022819

**Received** 28 March 2022; **Accepted** 22 July 2022; **Issue published** 23 November 2022

## Abstract

The doubly resolving sets are a natural tool to identify where diffusion occurs in a complicated network. Many real-world phenomena, such as rumour spreading on social networks, the spread of infectious diseases, and the spread of the virus on the internet, may be modelled using information diffusion in networks. It is obviously impractical to monitor every node due to cost and overhead limits because there are too many nodes in the network, some of which may be unable or unwilling to send information about their state. As a result, the source localization problem is to find the number of nodes in the network that best explains the observed diffusion. This problem can be successfully solved by using its relationship with the well-studied related minimal doubly resolving set problem, which minimizes the number of observers required for accurate detection. This paper aims to investigate the minimal doubly resolving set for certain families of Toeplitz graph*T*(1,

_{n}*t*), for

*t ≥*2 and

*n ≥ t +*2. We come to the conclusion that for

*T*(1, 2), the metric and double metric dimensions are equal and for

_{n}*T*(1, 4), the double metric dimension is exactly one more than the metric dimension. Also, the double metric dimension for

_{n}*T*(1, 3) is equal to the metric dimension for

_{n}*n =*5, 6, 7 and one greater than the metric dimension for

*n ≥*8.

## Keywords

1 Introduction and Preliminaries

To understand the abstract structure of graphs, graph invariants can be a powerful tool. Metric generators in graphs have evolved into a variety of distinct types based on their popularity or usefulness. As an example, virus propagation in complicated network difficulties can be detected using the double metric dimension (DMD).

We consider a finite, undirected, and connected graph

It is common in computer science, chemistry, biology, and operations research to structure graph theory models. In graph theory, the computation of the resolving sets and MD for general graphs is complex. In various disciplines, such as optimization, pattern recognition, and loran detecting devices, the MD has gained all the interest due to its applications.

Slater [1], a mathematician, was the first to discover the term MD. This notion was used to describe the study of the Loran or sonar model station. Another mathematician, Harary, independently described the concept of MD with the help of Harary et al. [2]. Additionally, this concept cleared the path for finding the unique recipient of a message on a network. Since then, several studies have been done on resolving sets, including [3,4]. Many different tasks can be accomplished with resolving sets, like network discovery and verification [5], strategies for the mastermind games [6], as well as digital geometry, pattern recognition, and processing of images [7]. The minimum order of a resolving set of Hamming graphs closely relates to the problem of weighing the coins discussed in [8,9]. Also, there are numerous applications in different fields, such as chemical structures [10], robotics [11], combinatorial optimization [12], geographic routing protocols [13] for the theoretical study of the MD.

The MD of any graph is a computationally difficult problem to solve. So, valuable bounds for different types of graphs have been found. The MD of all connected graphs, as well as the MD of certain well-known graph families, such as trees, pathways, and complete graphs, were established by Chartrand et al. [10,14]. For some families of generalized Petersen graphs, MD bounds were studied in [15]. The MD for chorded cycles and kayak paddles graphs was found to be constant by Ahmad et al. [16]. Many authors have extensively studied the MD of path-related graphs. The MD of the Kenser graph was computed by Hui et al. [17]. On the other hand, Alholi et al. [18] also contributed to this area by finding that the MD is constant. Buczkowski and others [19] presented a generic concept of k-dimensional graphs. The NP-completeness of the MD for general graphs was demonstrated by Khuller et al. [11]. The minimum order of a resolving set of Jahangir graphs has also been discussed in detail by Tomescu et al. [20].

Caceres et al. [21] developed the concept of doubly resolving sets (DRSs) of a graph

Therefore, DRSs are essential for studying the MD of Cartesian product graphs. These results have inspired us to work on finding the MDRSs. Also, MDRSs themselves have a unique combinatorial nature that can be seen in their integer programming model, which was shown in [22]. There are several families of graphs for which the problem of finding the MDRS has been examined. For example, MDRSs of prisms [23], convex polytopes [24], and Hamming graphs [25] have all been studied in the literature. The family of circulant graphs in [26] was found to have the same MD and MDRS. The MDRSs for the line graphs of prisms and sunlet graphs were found in [27]. For the first time, Chen et al. explicitly approximated the upper and lower bounds for the MDRS problem [28]. In [29], the minimal resolving sets and DMD of the line graph of chorded cycles were examined. Authors demonstrated that the DMD of

Our research is the continuation of the literature work mentioned earlier. We have investigated the DMD for some particular classes of Toeplitz graphs to contribute to our knowledge of this distance-based parameter in graphs. However, this variant is helpful in many fields, for instance, diffusion over the network, epidemics in human beings, the origin of a disease outbreak, etc. Using MDRSs, it is possible to identify the source of diffusion in complicated networks. Attempting to find the source of an infection in an extensive network might be difficult, but it is still an exciting challenge. For example, to detect the spread of the virus throughout a network, we need to know when specific nodes in the network are infected. However, maintaining observer nodes that can report their infection time may be costly. In addition, the position of a node in the network affects how much information it contains. Which nodes should we use as observers in order to increase our chances of correctly identifying the source? Because of its close relationship to another well-known DRS problem, we can reduce the number of observers required to achieve perfect detection even if the initial time at which an epidemic spreads is unknown [38,39].

Liu et al. [40] determined the MD of some families of Toeplitz graph

Theorem 1.1. For n ≥ 4, the metric dimension of Toeplitz graph

Theorem 1.2. For n ≥ 6, the metric dimension of Toeplitz graph

Theorem 1.3. For n ≥ 5, the metric dimension of Toeplitz graph

Detailed discussion of the rest of the article is provided in the following sections:

• Our discussion of Toeplitz graphs in Section 2 included the computation of MDRSs for the family of Toeplitz graphs

• The MDRSs for the family of Toeplitz graphs

• The MDRSs for the family of Toeplitz graph

• In Section 5, we conclude this article by expressing an opinion.

2 Minimal Doubly Resolving Sets for the Family of Toeplitz Graph

For a graph

It follows from Theorem 1.1 that

Due to the symmetry of

Due to the fact that, in order to calculate the distance between any pair of vertices in

Proof. Consider the case n = 2l, where l ≥ 2. We must prove that

It turns out that the value of the first metric coordinate of the vertex

Proof. Consider the case n = 2l + 1, where l ≥ 2. We must prove that

It turns out that the value of the first metric coordinate of the vertex

The main theorem is stated below by using Lemmas 2.1 and 2.2.

Theorem 2.1. Let

Example 2.1. For the Toeplitz graph

3 Minimal Doubly Resolving Sets for the Family of Toeplitz Graph

Specifically, in this part, we computed the MDRSs for the family of Toeplitz graph

It follows from Theorem 1.2 that

Due to the symmetry of

Lemma 3.1.

Proof. We already know that

Lemma 3.2. Let n ≡ 0(mod 4) and n ≥ 8, we have

Proof. Suppose that n ≡ 0(mod 4) and n ≥ 8. We need to prove that

It turns out that the value of the first metric coordinate of the vertex

Lemma 3.3. Let n ≡ 1(mod 4) and n ≥ 9, we have

Proof. Suppose that n ≡ 1(mod 4) and n ≥ 9. We need to prove that

It turns out that the value of the first metric coordinate of the vertex

Lemma 3.4. Let n ≡ 2(mod 4) and n ≥ 6, we have

Proof. Suppose that n ≡ 2(mod 4) and n ≥ 6. We need to prove that

It turns out that the value of the first metric coordinate of the vertex

Lemma 3.5. Let n ≡ 3(mod 4) and n ≥ 7, we have

Proof. Suppose that n ≡ 3(mod 4) and n ≥ 7. We need to prove that

It turns out that the value of the first metric coordinate of the vertex

The main theorem is stated below by using Lemmas 3.2–3.5.

Theorem 3.1. Let

4 Minimal Doubly Resolving Sets for the Family of Toeplitz Graph

Specifically, in this part, we computed the MDRSs for the family of Toeplitz graph

It follows from Theorem 1.3 that

To compute the distances between the vertices of the Toeplitz graph

Due to the symmetry of

Lemma 4.1.

Proof. We already know that

Lemma 4.2. Let n ≡ 0(mod 3) for n ≥ 6, we have

Proof. Suppose that n ≡ 0(mod 3) and n ≥ 6. Then, in the case n ≡ 0(mod 3) and n = 6, the MDRS for

It turns out that the value of the first metric coordinate of the vertex

Lemma 4.3. Let n ≡ 1(mod 3) for n ≥ 7, we have

Proof. Suppose that n ≡ 1(mod 3) and n ≥ 7. Then, in the case n ≡ 1(mod 3) and n = 7, the MDRS for

It turns out that the value of the first metric coordinate of the vertex

Lemma 4.4. Let n ≡ 2(mod 3) for n ≥ 5, we have

Proof. Suppose that n ≡ 2(mod 3) and n ≥ 5. Then, in the case n ≡ 1(mod 3) and n = 5, the MDRS for

It turns out that the value of the first metric coordinate of the vertex

The main theorem is stated below by using Lemmas 4.2–4.4.

Theorem 4.1. Let

Recently, some applications of DRSs can be seen to localizing the epidemic source in different complex networks such as social networks, epidemics in human beings and the origin of a disease outbreak, etc. (see [38,39]). In particular, we consider a network to reduce the number of observers using the DRSs in order to achieve the perfect detection of an epidemic source.

Let us assume, a social network arranged in the form of Toeplitz network

So, what are the fewest number of observers required to account epidemic source with an unknown starting time and irregular transmission delays among the nodes? Such that each node has a unique representation depending upon minimum distances from the observer nodes. In order to reduce the number of observers, we employed the MDRS

By using the Lemma 4.4 and Theorem 4.1, we placed the observers only on the nodes

This study is concerned with the concept of calculating MDRSs of graphs using an integer linear programming formulation that has been proposed earlier in the literature. In this article, we theoretically establish the MDRSs for the certain families of Toeplitz graphs

This research work may lead to the following open problem.

Open Problem 6.1. Investigate the minimal doubly resolving sets for the family of the generalized Toeplitz graphs

Acknowledgement: The authors are grateful to the editor and reviewers for the careful reading to improve the manuscript.

Funding Statement: The authors received no specific funding for this study.

Conflicts of Interest: The authors declare that they have no conflicts of interest to report regarding the present study.

## References

1. Slater, P. J. (1975). Leaves of trees. Congressus Numerantium, 14(549–559), 37.

2. Harary, F., Melter, R. A. (1976). On the metric dimension of a graph. Ars Combinatoria, 2, 191–195.

3. Chartrand, G., Erwin, D., Johns, G. L., Zhang, P. (2003). Boundary vertices in graphs. Discrete Mathematics, 263(1–3), 25–34.

4. Chartrand, G., Zhang, P. (2003). The theory and applications of resolvability in graphs. A survey. Congress us Numerantium, 1, 47–68.

5. Beerliova, Z., Eberhard, F., Erlebach, T., Hall, A., Hoffmann, M. et al. (2006). Network discovery and verification. IEEE Journal on Selected Areas in Communications, 24(12), 2168–2181.

6. Chvatal, V. (1983). Mastermind. Combinatorica, 3(3), 325–329.

7. Melter, R. A., Tomescu, I. (1984). Metric bases in digital geometry. Computer Vision, Graphics, and Image Processing, 25(1), 113–121.

8. Erdos, P., Renyi, A. (1963). On two problems of information theory. Magyar Tudományos Akadémia Matematikai És Fizikai Osztalyanak, 8, 229–243.

9. Lindström, B. (1964). On a combinatory detection problem I. Magyar Tudományos Akadémia Matematikai És Fizikai Osztalyanak, 9, 195–207.

10. Chartrand, G., Eroh, L., Johnson, M. A., Oellermann, O. R. (2000). Resolvability in graphs and the metric dimension of a graph. Discrete Applied Mathematics, 105(1--3), 99–113.

11. Khuller, S., Raghavachari, B., Rosenfeld, A. (1996). Landmarks in graphs. Discrete Applied Mathematics, 70(3), 217–229.

12. Sebo, A., Tannier, E. (2004). On metric generators of graphs. Mathematics of Operations Research, 29(2), 383–393.

13. Liu, K., Abu-Ghazaleh, N. (2006). Virtual coordinates with backtracking for void traversal in geographic routing. International Conference on Ad-Hoc Networks and Wireless, pp. 46–59. Berlin, Heidelberg: Springer.

14. Chartrand, G., Poisson, C., Zhang, P. (2000). Resolvability and the upper dimension of graphs. Computers and Mathematics with Applications, 39(12), 19–28.

15. Shao, Z., Sheikholeslami, S. M., Wu, P., Liu, J. B. (2018). The metric dimension of some generalized petersen graphs. Discrete Dynamics in Nature and Society, 2018, 1–10.

16. Ahmad, A., Baca, M., Sultan, S. (2020). Computing the metric dimension of kayak paddles graph and cycles with chord. Proyecciones, 39(2), 287–300.

17. Hui, P., Xunting, W., Jing, W., Siyuan, C. (2016). The metric dimension of some kneser graphs. Journal of Computational and Theoretical Nanoscience, 13(5), 3013–3018.

18. Alholi, M. M., Abughneim, O. A., Ezeh, H. A. (2017). Metric dimension of some path related graphs. Global Journal of Pure and Applied Mathematics, 3(2), 149–157.

19. Buczkowski, P. S., Chartrand, G., Poisson, C., Zhang, P. (2003). On k-dimensional graphs and their bases. Periodica Mathematica Hungarica, 46(1), 9–15.

20. Tomescu, I., Javaid, I. (2007). On the metric dimension of the jahangir graph. Bulletin Mathématiques de la Société des Sciences Mathématiques de Roumanie, 50(4), 371–376.

21. Cáceres, J., Hernando, C., Mora, M., Pelayo, I. M., Puertas, M. L. et al. (2007). On the metric dimension of cartesian products of graphs. SIAM Journal on Discrete Mathematics, 21(2), 423–441.

22. Kratica, J., Cangalovic, M., Kovacevic-Vujcic, V. (2009). Computing minimal doubly resolving sets of graphs. Computers and Operations Research, 36(7), 2149–2159.

23. Cangalovic, M., Kratica, J., Kovacevic-Vujcic, V., Stojanovic, M. (2013). Minimal doubly resolving sets of prism graphs. Optimization, 62(8), 1037–1043.

24. Kratica, J., Kovacevic-Vujcic, V., Cangalovic, M., Stojanovic, M. (2012). Minimal doubly resolving sets and the strong metric dimension of some convex polytopes. Applied Mathematics and Computation, 218(19), 9790–9801.

25. Kratica, J., Kovacevic-Vujcic, V., Cangalovic, M., Stojanovic, M. (2012). Minimal doubly resolving sets and the strong metric dimension of hamming graphs. Applicable Analysis and Discrete Mathematics, 6(1), 63–71.

26. Ahmad, A., Sultan, S. (2017). On minimal doubly resolving sets of circulant graphs. Acta Mechanica Slovaca, 21(1), 6–11.

27. Ahmad, M., Zahid, Z., Zafar, S. (2018). On minimal edge version of doubly resolving sets of a graph. arXiv preprint arXiv:1807.02365.

28. Chen, X., Hu, X., Wang, C. (2016). Approximation for the minimum cost doubly resolving set problem. Theoretical Computer Science, 609, 526–543.

29. Ahmad, M., Zahid, Z., Rashid, T., Guirao, J. L. G. (2022). Computing edge version of resolvability and double resolvability of a graph. Journal of Chemistry, 2022, 1–11.

30. Ahmad, M., Ameen, N., Zahid, Z., Zafar, S. (2020). Computing edge version of metric and double metric dimensions of kayak paddle graphs. Discrete Mathematics, Algorithms and Applications, 12(5), 2050070.

31. Ahmad, M., Alrowaili, D., Zahid, Z., Siddique, I., Iampan, A. (2022). Minimal doubly resolving sets of some classes of convex polytopes. Journal of Mathematics, 2022.

32. Pan, L., Ahmad, M., Zahid, Z., Zafar, S. (2021). Computation of the double metric dimension in convex polytopes. Journal of Mathematics, 2021, 1–11.

33. Ahmad, A., Baca, M., Sultan, S. (2019). On the minimal doubly resolving sets of Harary graph. Acta Mathematica Universitatis Comenianae, 89(1), 123–129.

34. Liu, J. B., Zafari, A. (2020). Computing minimal doubly resolving sets and the strong metric dimension of the layer sun graph and the line graph of the layer sun graph. Complexity, 2020, 1–8.

35. Ahmad, A., Baca, M., Sultan, S. (2018). Minimal doubly resolving sets of necklace graph. Mathematical Reports, 2, 123–129.

36. Liu, J. B., Zafari, A., Zarei, H. (2020). Metric dimension, minimal doubly resolving sets, and the strong metric dimension for jellyfish graph and cocktail party graph. Complexity, 2020, 1–7.

37. Liu, J. B., Zahid, Z., Nasir, R., Nazeer, W. (2018). Edge version of metric dimension and doubly resolving sets of the necklace graph. Mathematics, 6(11), 243.

38. Spinelli, B., Celis, L. E., Thiran, P. (2016). Observer placement for source localization: the effect of budgets and transmission variance. 2016 54th Annual Allerton Conference on Communication, Monticello, IL, USA, Control, and Computing (Allerton), pp. 743–751. IEEE. DOI 10.1109/ALLERTON.2018.8635897.

39. Spinelli, B., Celis, L. E., Thiran, P. (2018). How many sensors to localize the source? the double metric dimension of random networks. 2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 1036–1043. Monticello, IL, USA. IEEE. DOI 10.1109/ALLERTON.2018.8635897.

40. Liu, J. B., Nadeem, M. F., Siddiqui, H. M. A., Nazir, W. (2019). Computing metric dimension of certain families of toeplitz graphs. IEEE Access, 7, 126734–1267.

## Cite This Article

**APA Style**

*Computer Modeling in Engineering & Sciences*,

*135*

*(3)*, 2681-2696. https://doi.org/10.32604/cmes.2023.022819

**Vancouver Style**

**IEEE Style**

*Comput. Model. Eng. Sci.*, vol. 135, no. 3, pp. 2681-2696, 2023. https://doi.org/10.32604/cmes.2023.022819

This work is licensed under a Creative Commons Attribution 4.0 International License , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.