Abstract
The metric representation of a vertex of a graph is a finite vector representing distances of with respect to vertices of some ordered subset . If no suitable subset of provides separate representations for each vertex of , then the set is referred to as a minimal resolving set. The metric dimension of is the cardinality of the smallest (with respect to its cardinality) minimal resolving set. A resolving set is secure if for any , there exists such that is a resolving set. For various classes of graphs, the value of the secure resolving number is determined and defined. The secure metric dimension of the graph classes is being studied in this work. The results show that different graph families have different metric dimensions.
Highlights
- Determining and defining the value of the secure resolving number of a resolving set for various classes of graph.
- Studying the secure metric dimension of the graph classes.
- Demonstrating how various graph families can have varying metric dimensions.
1. Introduction
Let be a connected, simple, finite graph. On which the ordering is imposed, let . The metric description of with regard to is defined as the ordered -tuples for each . If implies for every , then the set is referred to as a resolving set of . A minimal resolving set, also known as a basis, is a resolving set of with minimum cardinality. The dimension of , represented by , is the cardinality of a minimum resolving set [1].
There is previous study in the literature on the location of sets in a connected graph [2, 3]. Nearly forty years ago, Slater introduced the idea of finding sets (resolving sets) and a reference set (metric dimension). Afterwards, the aforementioned theory [4] was independently discovered by Harary and Melter. They started referring to location numbers as metric dimensions. On resolving sets, resolving dominating sets, independent resolving sets, etc., many papers have been composed. In a graph, the concept of security is linked to many kinds of sets. A dominating set of is a secure set, for instance, if there is an such that is a dominating set for any [5, 6]. Farooq et al. [7] studied the metric dimension of the line graph of the Bakelite network and subdivided the Bakelite network. According to [8], a path graph is the only graph with a metric dimension of 1. For , the metric dimension of the cycle graph is 2. This idea is especially helpful for applications including chemistry and space routing. For instance, in space routing, the objective is to assign the smallest number of robots feasible to certain vertices so that they can visit each vertex exactly once. The problem can be resolved by applying the idea of metric dimension. The minimal landmarks needed for the hexagonal network and the honeycomb network are three and six, respectively, according to research by Abbas et al. [9]. The local metric dimension of a number of specific line graphs was examined by Yang et al. [10]. Jothi et al. [11] investigated the relation between the metric dimension of a bipartite graph and its projections. Additionally, they provided some realization results for the bounds on the metric dimension of a bipartite graph. The dominant metric dimension of the generalized Petersen graph was examined by Susilowati et al. [12]. Mazidah et al. [13] examined the resolving independent domination number of path graph, cycle graph, friendship graph, helm graph and fan graph. The maximum number of vertices in a bipartite graph with a particular diameter and metric dimension was computed by Dankelmann et al. [14]. Additional details can be discovered in the literature [15-19].
Our main aim in this paper is to compute the secure resolving set of some graphs, including the join of Kite graph, the 1-join of square of path graph, coconut tree and extended jewel graph.
Definition 1.1 The basis of the graph is the resolving set with the least vertices [7].
Definition 1.2 [20]: A Kite graph is made up of a cycle of length with edges and a path connected to one of the cycle's vertices.
Definition 1.3 [21]: A Coconut tree : for any positive integers and is derived from the path by attaching additional pendant edges at an end vertex of .
Illustration 1.3. Consider , for which . Then, is resolving, and for any , there exists such that is a resolving set of . It can be easily seen that .
Fig. 1An example on a Kite graph
![An example on a Kite graph](https://static-01.extrica.com/articles/24168/24168-img1.jpg)
2. Secure resolving dimension for several known graphs [5, 6]
1. .
2. .
3. , .
4. ,
5. .
6. For Trapezoid graph , and , for all .
7. For graph, and .
8. For Tortoise graph , and .
9. .
3. Main results
Here, we demonstrate that the secure metric dimension of including the join of Kite graph, the 1-join of square of path graph, coconut tree and extended jewel graph. We also derive the explicit formulas for the secure metric dimension of shadow graph of path , Jelly fish , Lilly graph , Twig graph , Joint sum of two copies of , quadrilateral graphs and subdividing all the edges of .
Theorem 3.1: Let is Join of Kite graph with vertices and be a secure metric basis of , then .
Fig. 2Join of (m, n) Kite graph Km,n
![Join of (m, n) Kite graph Km,n](https://static-01.extrica.com/articles/24168/24168-img2.jpg)
Proof. The secure resolving set in general form is . The following are representations of the vertices with respect to :
Since all vertices have unique representations, we obtain .
Theorem 3.2: Let is 1-join of square of path with vertices and be a secure metric basis of , then .
Fig. 31-join of square of path Pn2
![1-join of square of path Pn2](https://static-01.extrica.com/articles/24168/24168-img3.jpg)
Proof. We label the 1-join of square of path as shown in Fig. 2 such that is the vertices number. It is clear that is . Let .
Begin
,
for
end
for
)=
end
for
end
for
end
end
This completes the proof.
Theorem 3.3: If , , is coconut tree, then .
Proof. The secure resolving set in general form is . The representations of vertices in regard to are as follow.
We choose a subset , and we must demonstrate that for and . We obtained the representations of vertices in graph with respect to are:
Fig. 4Coconut tree CT(m, n)
![Coconut tree CT(m, n)](https://static-01.extrica.com/articles/24168/24168-img4.jpg)
The representations of vertices in graph are distinct as seen above. This implies that is secure resolving set, but this does not prove that it is the lower bound. As a result, the upper bound is . Now, we demonstrate that . Let be a secure resolving set with . Assume that is another minimal resolving set, or .
If we select an ordered set , , , so that there exist two vertices such that . is not a secure resolving set, which is contrary to assumption. As a result, is the lower bound. From the above proving, we conclude that .
Theorem 3.4: If , , is extended jewel graph, then .
Proof. We choose a subset , and we must demonstrate that for . We obtained the representations of vertices in graph with respect to are:
The representations of vertices in graph are distinct as seen above. This implies that is secure resolving set, but this does not prove that it is the lower bound. As a result, the upper bound is . Now, we demonstrate that . Let be a secure resolving set with . Assume that is another minimal resolving set, or .
If we select an ordered set , , , so that there exist two vertices such that . It should be noted that is not a secure resolving set, which is contrary to assumption. As a result, is the lower bound. From the above proving, we conclude that .
Fig. 5Extended jewel graph E(jn )
![Extended jewel graph E(jn )](https://static-01.extrica.com/articles/24168/24168-img5.jpg)
4. Secure resolving dimension for special classes of graphs
Corollary 4.1 If is a shadow graph of path of order , then .
Corollary 4.2 If is Jelly fish of order , then .
Corollary 4.3 If is Lilly graph , , then .
Corollary 4.4 If is Twig graph , , then .
Corollary 4.5 If is Joint sum of two copies of , then .
Corollary 4.6 If is quadrilateral graphs , , then .
Corollary 4.7 If is subdividing all the edges of , , then .
5. Conclusions
The secure metric dimension of a graph is an NP-complete problem. The present study starts with the task of finding the secure metric dimension of new graph types. The secure metric dimensions of the join of the kite graph and the 1-join of the square of the path graph have the same secure metric dimensions. The secure metric dimension of the coconut tree and the extended jewel graph have different secure metric dimensions. Additionally, we deduced the exact formulas for the joint total of two copies of , quadrilateral graphs , Jelly fish , Lilly graph , Twig graph , and subdividing all the edges of .
In the future, we plan to determine the secure metric dimension of many graphs, such as subdivisions of crown graphs, twig graph, Lilly graph and jelly fish graph. Many other ideas can be inspired from the references [22-25].
References
-
G. Chartrand, L. Eroh, M. A. Johnson, and O. R. Oellermann, “Resolvability in graphs and the metric dimension of a graph,” Discrete Applied Mathematics, Vol. 105, No. 1-3, pp. 99–113, Oct. 2000, https://doi.org/10.1016/s0166-218x(00)00198-0
-
P. J. Slater, “Domination and location in acyclic graphs,” Networks, Vol. 17, No. 1, pp. 55–64, Oct. 2006, https://doi.org/10.1002/net.3230170105
-
S. J. Seo and P. J. Slater, “Open neighborhood locating dominating sets,” Australasian Journal of Combinatorics, Vol. 46, pp. 109–119, 2010.
-
R. C. Brigham, G. Chartrand, R. D. Dutton, and P. Zhang, “Resolving domination in graphs,” Mathematica Bohemica, Vol. 128, No. 1, pp. 25–36, Jan. 2003, https://doi.org/10.21136/mb.2003.133935
-
B. Mohamed and M. Amin, “Domination number and secure resolving sets in cyclic networks,” Applied and Computational Mathematics, Vol. 12, No. 2, pp. 42–45, May 2023, https://doi.org/10.11648/j.acm.20231202.12
-
H. Subramanian and S. Arasappan, “Secure resolving sets in a graph,” Symmetry, Vol. 10, No. 10, p. 439, Sep. 2018, https://doi.org/10.3390/sym10100439
-
M. U. Farooq, A. U. Rehman, T. Q. Ibrahim, M. Hussain, A. H. Ali, and B. Rashwani, “Metric dimension of line graphs of Bakelite and subdivided Bakelite network,” Discrete Dynamics in Nature and Society, Vol. 2023, pp. 1–6, Aug. 2023, https://doi.org/10.1155/2023/7656214
-
I. Javaid, M. T. Rahim, and K. Ali, “Families of regular graphs with constant metric dimension,” Utilitas Mathematica, Vol. 75, No. 1, pp. 21–33, 2008.
-
S. Abbas, Z. Raza, N. Siddiqui, F. Khan, and T. Whangbo, “Edge metric dimension of honeycomb and hexagonal networks for IoT,” Computers, Materials and Continua, Vol. 71, No. 2, pp. 2683–2695, Jan. 2022, https://doi.org/10.32604/cmc.2022.023003
-
C. Yang, X. Deng, and W. Li, “On the local metric dimension of line graphs,” Journal of Interconnection Networks, Vol. 2023, p. 23500, Oct. 2023, https://doi.org/10.1142/s0219265923500263
-
M. Anandha Jothi and K. Sankar, “On the metric dimension of bipartite graphs,” AKCE International Journal of Graphs and Combinatorics, Vol. 20, No. 3, pp. 287–290, Sep. 2023, https://doi.org/10.1080/09728600.2023.2223248
-
L. Susilowati, I. W. Mufidah, and N. Estuningsih, “The dominant metric dimension of generalized Petersen graph,” in 4th International Scientific Conference of Alkafeel University (ISCKU 2022), Vol. 2975, No. 1, p. 02000, Jan. 2023, https://doi.org/10.1063/5.0181076
-
T. Mazidah, Dafik, Slamin, I. H. Agustin, and R. Nisviasari, “Resolving independent domination number of some special graphs,” Journal of Physics: Conference Series, Vol. 1832, No. 1, p. 012022, Mar. 2021, https://doi.org/10.1088/1742-6596/1832/1/012022
-
P. Dankelmann, J. Morgan, and E. Rivett-Carnac, “Metric dimension and diameter in bipartite graphs,” Discussiones Mathematicae Graph Theory, Vol. 43, No. 2, p. 487, Jan. 2020, https://doi.org/10.7151/dmgt.2382
-
B. Mohamed, L. Mohaisen, and M. Amin, “Binary Archimedes optimization algorithm for computing dominant metric dimension problem,” Intelligent Automation and Soft Computing, Vol. 38, No. 1, pp. 19–34, Jan. 2023, https://doi.org/10.32604/iasc.2023.031947
-
I. M. Batiha and B. Mohamed, “Binary rat swarm optimizer algorithm for computing independent domination metric dimension problem,” Mathematical Models in Engineering, Vol. 10, No. 3, p. 13, Apr. 2024, https://doi.org/10.21595/mme.2024.24037
-
D. A. Mojdeh, I. Peterin, B. Samadi, and I. G. Yero, “On three outer-independent domination related parameters in graphs,” Discrete Applied Mathematics, Vol. 294, pp. 115–124, May 2021, https://doi.org/10.1016/j.dam.2021.01.027
-
B. Mohamed and M. Amin, “A hybrid optimization algorithms for solving metric dimension problem,” SSRN Electronic Journal, Vol. 2023, pp. 1–10, Jan. 2023, https://doi.org/10.2139/ssrn.4504670
-
B. Mohamed and M. Amin, “The metric dimension of subdivisions of Lilly graph, tadpole graph and special trees,” Applied and Computational Mathematics, Vol. 12, No. 1, pp. 9–14, Mar. 2023, https://doi.org/10.11648/j.acm.20231201.12
-
S. Sriram and R. Govindarajan, “Permutation labeling of joins of Kite graph,” International Journal of Computer Engineering and Technology, Vol. 10, No. 3, pp. 1–8, May 2019, https://doi.org/10.34218/ijcet.10.3.2019.001
-
S. M. and V. K., “Vertex edge neighborhood prime labeling of some graphs,” Malaya Journal of Matematik, Vol. 7, No. 4, pp. 775–785, Jan. 2019, https://doi.org/10.26637/mjm0704/0024
-
M. I. Batiha, M. Amin, B. Mohamed, and H. I. Jebril, “Connected metric dimension of the class of ladder graphs,” Mathematical Models in Engineering, Vol. 10, No. 2, Apr. 2024, https://doi.org/10.21595/mme.2024.23934
-
H. Al-Zoubi, H. Alzaareer, A. Zraiqat, T. Hamadneh, and W. Al-Mashaleh, “On ruled surfaces of coordinate finite type,” WSEAS Transactions on Mathematics, Vol. 21, pp. 765–769, Nov. 2022, https://doi.org/10.37394/23206.2022.21.87
-
I. M. Batiha, S. A. Njadat, R. M. Batyha, A. Zraiqat, A. Dababneh, and S. Momani, “Design fractional-order PID controllers for single-joint robot arm model,” International Journal of Advances in Soft Computing and its Applications, Vol. 14, No. 2, pp. 97–114, Aug. 2022, https://doi.org/10.15849/ijasca.220720.07
-
I. M. Batiha et al., “Tuning the fractional-order PID-Controller for blood glucose level of diabetic patients,” International Journal of Advances in Soft Computing and its Applications, Vol. 13, No. 2, pp. 1–10, 2021.
About this article
The authors have not disclosed any funding.
The datasets generated during and/or analyzed during the current study are available from the corresponding author on reasonable request.
Iqbal M. Batiha: conceptualization, validation, data curation. Basma Mohamed: methodology, formal analysis, software, investigation. Iqbal H. Jebril: resources, visualization, supervision.
The authors declare that they have no conflict of interest.