Published: 31 July 2024

A special graph for the connected metric dimension of graphs

Iqbal M. Batiha1
Nidal Anakira2
Amal Hashim3
Basma Mohamed4
1Department of Mathematics, Al Zaytoonah University of Jordan, Amman, 11733, Jordan
1Nonlinear Dynamics Research Center (NDRC), Ajman University, Ajman, 346, United Arab Emirates
2Faculty of Education and Arts, Sohar University, Sohar, 3111, Oman
2Jadara Research Center, Jadara University, P.O. Box 733, Irbid, 21110, Jordan
3, 4Giza Higher Institute for Managerial Sciences, Tomah, Egypt
Corresponding Author:
Iqbal M. Batiha
Views 50
Reads 22
Downloads 75

Abstract

Given a connected graph G=(V, E), let d(x, y) represent the separation between x and y at its vertices. If each vertex in a collection B is uniquely identified by its vector of distances to the vertices in B, then that set of vertices resolves a graph G. A metric dimension of G is represented by dim(G) and is the smallest cardinality of a resolving set of G. If the subgraph B- induced by B is a nontrivial connected subgraph of G, then a resolving set B of G is connected. The metric dimension of G is the cardinality of the minimal resolving set, while the connected metric dimension of G is the cardinality of the smallest connected resolving set. The connected metric dimension of the knots graph, whitehead link graph and jewel graph are determined in this study. Finally, we derive the explicit formulas for the triangular book graph, quadrilateral book graph and crystal planar map.

A special graph for the connected metric dimension of graphs

Highlights

  • Determining the connected metric dimension of the knots graph.
  • Determining the connected metric dimension of the whitehead link graph and jewel graph.
  • Deriving some explicit formulas for the triangular book graph, quadrilateral book graph and crystal planar map.

1. Introduction

The length of the shortest path between any two vertices in a connected graph G=(V, E), where V is the set of vertices and E is the set of edges, is indicated by the distance d(u,v). For any given b, the k-vector r(v|b)=(d(v,b1), d(v,b2),..., d(v, bk)) is the metric representation of v. If there is a unique representation for every pair of G vertices in r(v |b), then B is a resolving set. Among all the resolving sets of G, dim(G), the metric dimension of G, has the least cardinality. A metric basis is a resolving set with low cardinality. Landmarks are the vertices of G on a metric basis.

A minimum resolving set, also known as a metric basis for G, is a resolving set that has the smallest cardinality for G. The metric dimension of G, which is represented as dim(G). The problem of figuring out the metric dimension of a graph was tackled by Harary et al. [1]. Slater discussed the use of this concept to long-range navigational aids [2]. Melter et al. [3] studied the metric dimension problem of grid graphs. Khulller et al. have also investigated the metric dimension problem for trees and multi-dimensional grids [4]. They also talked about how the idea of metric dimension is used in robot navigation. Note that G+H represents the connecting point of two graphs, H and G, and for n1, fn=K1+Pn represents a fan. The metric dimension of fan fn was discovered by Caceres et al. [5]. The Jahangir graph, denoted as J2n with n2, is the graph that is produced from a wheel W2n by removing n alternate spokes. It is also sometimes referred to as the gear graph.

The metric dimension of the Jahangir graph J2n, as well as the partition and connected dimension of the wheel graph Wn were calculated by Tomescu et al. [6]. Paths on n vertices constitute a family of graphs with constant metric dimension since Chartrand et al. demonstrated in [7] that a graph G has metric dimension 1 if and only if G=Pn. According to Javaid et al. in [8], the planar graph Antiprism An is a family of regular graphs with a constant metric dimension such that for any n5, dim(An)=3. Ahmad et al. [9] calculated the metric dimension of P(n,2)ʘK1. Sooryanarayana et al. [10] created various types of r-sets and determined the minimal cardinality of these sets. Singh et al. [11] computed the metric and edge metric dimensions of the Dutch and French windmill graphs, two types of windmill graphs. Susilowati et al. [12] computed the complement metric dimension of the corona and comb products graphs. Wijaya et al. [13] introduced a simple method for creating new Ramsey minimal graphs from known Ramsey minimal graphs by applying a subdivision operation. A computer program and an algorithm were developed by Muhammad et al. [14] to determine the base and dimension of a network. Rehman et al. [15] gave explicit formulae for the metric dimension of Arithmetic Graph Am when m has exactly two distinct prime divisors. They gave restrictions on the metric dimension of Am when m has at least three distinct prime divisors. Feng et al. [16] examined the metric dimension of the power graph of a finite group. The exact value of the metric dimension of Andrásfai graphs was found by Pejman et al. [17]. The constant metric dimension of Pn(1,2,3) and Mn was obtained by Ali et al. [18], while the k-metric dimension of linked corona graphs was found to have tight limitations and closed formulas by Moreno et al. [19].

The metric dimensions of a number of graphs, including the Tadpole, Lilly, and special trees (star, bistar, and coconut trees), were ascertained by Mohamed et al. [20]. In addition to giving a summary of several metric dimension findings and uses, Mohamed [21] offered a self-contained introduction to the metric dimension. The tortoise network, the open ladder network, the Z-(Pn) network, and the trapezoid network were among the networks that Mohamed et al. [22] investigated. The connected metric dimension is defined in [23, 24].

In [23], the connected metric dimension of path graph Pn, cycle graph Cn, wheel graph Wn, star graph K1,n-1, and complete graph Kn is investigated. It is shown that the connected metric dimension of cycle graph Cn,n3 is 2, wheel graph Wn, n7 is 2n+25+1, star graph K1,n-1, n4 is n1, complete graph Kn, n3is n-1andpath graph Pn, n2 is 2. In [24], it is shown that the connected metric dimension at a vertex of tree Tis 1 if v is an end vertex and 2 if v is not an end vertex, Petersen graph P is 4, and wheel graph Wn, n7 is 2n+25+1. For further information, see the literature [25-37]. This work determines the connected metric dimension of knot graphs, whitehead link graphs and jewel graph. Finally, we derive the explicit formulas for the triangular book graph, quadrilateral book graph and crystal planar map.

2. Definitions and basic terminology

Definition 1. [32] A link L is an embedding of a topological sum of finitely many copies of a circle S1 into three-dimensional topological space R3, L:S1S1S1...S1R3. The restriction of L to one of the copies of S1 is called a component of L. Note that each component of a link is a Knot.

Definition 2. [32] An illustration of a knot or link is a projection of the latter into a plane that shows the markings for each crossing (over- or under-crossing) in the projection’s image. This indicates that a knot diagram is an image of a knot projected onto a plane; a diagram in R2 is composed of several arcs and crossings. It did not permit the following at a crossing where one arc is the over pass and the other forms an under pass.

Fig. 1A diagram of knot or link

A diagram of knot or link
A diagram of knot or link
A diagram of knot or link

Definition 3. [32] A graph of a knot or link diagram is made up of crossings acting as the graphs' vertices and the arcs connecting two crossings acting as its edges.

Definition 4. An alternating knot An is a knot with a knot diagram where crossings alternate between overpasses and underpasses. Alternating diagrams are not required for all knot diagrams of alternating knots. All prime knots with seven or fewer crossings are alternating knots, as are the trefoil and figure-eight knots.

We may observe that for n=7, every link graph includes at least two multiple edges based on the occurrence of many edges in the graph. In a link graph with an even number of vertices (n=8,10,), there are always samples with a single edge. Using the same method as for the 17th-link graph for n = 6, we can observe this.

Fig. 2Series of link graph starting by chain Borromean ring without any multiple edge

Series of link graph starting by chain Borromean ring without any multiple edge

a)n= 6

Series of link graph starting by chain Borromean ring without any multiple edge

b)n= 8

Series of link graph starting by chain Borromean ring without any multiple edge

c)n= 10

The Whitehead link graph starts the following series of n-crossing, n5, 2-component link graphs.

Fig. 3Series of link graph starting by chain Borromean ring

Series of link graph starting by chain Borromean ring

3. Applications of knots graph

First, knot theory provides a wealth of examples for several areas of topology, including geometric group theory and specific types of algebra. The second is a list of scientific and engineering uses, such as separating DNA, combining liquids, and understanding the Sun’s corona structure. Knot invariants arise in many forms, including integers, polynomials, and homology theories.

4. Main results

Corollary 1. Let G is triangular book graph Tn with n vertices, then cdim(Tn)=n-2.

Corollary 2. Let G is quadrilateral book graph Bn4 with n vertices, then cdim(Bn4)=n2.

Theorem 3. Let G is Knots graph Kn with n vertices, then cdim(Kn)=3 as shown in Fig. 4.

Proof. We label Kn as shown in Fig. 4. It is clear that the number of vertices is n. Let w=v1,v2,v3. So that the proof has two cases:

Case (1). The representation of the vertices when n=6,10,14, are as follows:

1
rviB-=0,1,1,i=1,1,0,1,i=2,i-12,i-12,i-32,3i+2n 2,i2,i-22,i-22,4i+2n2+1,n-24,n+24,n-24,i=n2+2,n-i+22,n-i+22,n-i+42,n2+3i+2n,n-i+12,n-i+32,n-i+32,n2+4i+2n-1.

Fig. 4Knots graph Kn

Knots graph Kn

Case (2). The representation of the vertices when n=8,12,16, are as follows:

2
rviB-=0,1,1,i=1,1,0,1,i=2,i-12,i-12,i-32, 3i+2n 2+1,i2,i-22,i-22,4i+2n,n4,n4,n4-1, i=n2+1,n-i+22,n-i+22,n-i+22, i= n2+2,n-i+12,n-i+32,n-i+32,n2+3i+2n-1,n-i+22,n-i+22,n-i+42,n2+4i+2n.

Clearly, the induced subgraph of B- is connected and the representations of vertices in Kn graph are distinct as shown above, this implies that B- is conncted resolving set, but it is not necessarily the lower bound. Hence, an upper bound is cdim(Kn)3. So, we show that cdim(Kn)3. Let B-=v1,v2,v3 be a connected resolving set with B-=3. Assume that B-1 is another minimal connected resolving set. If we select an ordered set B-1B--{vi,vj}, 1 i, j3, ij, so that there exist two vertices vi,vjKn such that r(vi|B-)=r(vj|B-)=(1,1,, 1). It should be noted that B-1 is not a connected resolving set, which is contrary to the assumption. As a result, cdim(Kn)3 is the lower bound. In conclusion cdim(Kn)=3.

Theorem 4. Let wln is whitehead link graph with n vertices, then cdim(wln)=3 as shown in Fig. 5.

Fig. 5Whitehead link graph wln

Whitehead link graph wln

Proof. We label wln as shown in Fig. 5. It is clear that the number of vertices is n. Let B-=v1,v2,v3. So that the proof has two cases:

Case (1). The representation of the vertices when n=7,9,11, are as follows:

3
rviB-=0,1,1,i=1,i-1,i-2,i,2i+2n-32,n-32,n-52,n-32,i=n-1 2,n-32,n-32,n-52,i=n+12,n-i-1,n-i,n-i-2,n+32in-4,1,2,0,i= n-3,2,3,1, i=n-2,1,2,1,i=n-1,2,3,2,i=n.

Case (2). The representation of the vertices when n=8,10,12, are as follows:

4
rviB-=0,1,1,i=1,i-1,i-2,i,2i+2n-22,n-22,n-42,n-42,i=n 2,n-i-1,n-i,n-i-2,n2+1in-4,1,2,0, i= n-3,2,3,1,i=n-2,1,2,1,i=n-1,2,3,2,i=n.

Corollary 5. Let G be a crystal planar map Cn with n vertices where k blocks, then cdim(Cn)=3.

Theorem 6. Let G be a jewel graph Jn with k blocks and n vertices, then cdim(Jn) =2.

Fig. 6Jewel graph Jn

Jewel graph Jn

Proof. We label a jewel graph Jn as shown in Fig. 6. It is clear that the number of vertices is n=k+3 and k is the number of blocks of G. Let B-=v1,v3.

Begin

j= 2

for i= 1: 3

dvi,B-=i-1,j

j=j-1

end

for i=4:n

dvi,B-=1,1

end

end

5. Conclusions

Metric dimension is used in many fields, including image processing, combinatorial optimization, robot navigation, network discovery and verification, and wireless sensor network localization. The connected metric dimension of the knots graph, whitehead link graph and jewel graph are determined in this study. Finally, we derived the explicit formulas for the triangular book graph, quadrilateral book graph and crystal planar map.

References

  • F. Harary and R. A. Melter, “On the metric dimension of a graph,” Ars Combinatoria, Vol. 2, pp. 191–195, 1976.
  • P. J. Slater, “Leaves of trees,” Congressus Numerantium, Vol. 14, pp. 549–559, 1975.
  • R. A. Melter and I. Tomescu, “Metric bases in digital geometry,” Computer Vision, Graphics, and Image Processing, Vol. 25, No. 1, pp. 113–121, Jan. 1984, https://doi.org/10.1016/0734-189x(84)90051-3
  • S. Khuller, B. Raghavachari, and A. Rosenfeld, “Landmarks in graphs,” Discrete Applied Mathematics, Vol. 70, No. 3, pp. 217–229, Oct. 1996, https://doi.org/10.1016/0166-218x(95)00106-2
  • C. Hernando, M. Mora, I. M. Pelayo, C. Seara, J. Cáceres, and M. L. Puertas, “On the metric dimension of some families of graphs,” Electronic Notes in Discrete Mathematics, Vol. 22, pp. 129–133, Oct. 2005, https://doi.org/10.1016/j.endm.2005.06.023
  • I. Tomescu, I. Javaid, and I. Slamin, “On the partition dimension and connected partition dimension of wheels,” Ars Combinatoria, Vol. 84, pp. 311–318, 2007.
  • 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
  • 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.
  • Z. Ahmad, M. A. Chaudhary, A. Q. Baig, and M. A. Zahid, “On metric dimension of P(n,2)ʘK1 graph,” Journal of Discrete Mathematical Sciences and Cryptography, Vol. 24, No. 2, pp. 629–645, Feb. 2021, https://doi.org/10.1080/09720529.2021.1907017
  • B. Sooryanarayana, S. A. S., and C. S. B., “Certain varieties of resolving sets of a graph,” Journal of the Indonesian Mathematical Society, Vol. 27, No. 1, pp. 103–114, Mar. 2021, https://doi.org/10.22342/jims.27.1.881.103-114
  • P. Singh, S. Sharma, S. K. Sharma, and V. K. Bhat, “Metric dimension and edge metric dimension of windmill graphs,” AIMS Mathematics, Vol. 6, No. 9, pp. 9138–9153, Jan. 2021, https://doi.org/10.3934/math.2021531
  • L. Susilowati, R. A. Slamin, and A. Rosfiana, “The complement metric dimension of graphs and its operations,” International Journal of Civil Engineering and Technology, Vol. 10, No. 3, pp. 2386–2396, 2019.
  • K. Wijaya, E. T. Baskoro, H. Assiyatun, and D. Suprijanto, “Subdivision of graphs in R(mK2,P4),” Heliyon, Vol. 6, No. 6, p. e03843, Jun. 2020, https://doi.org/10.1016/j.heliyon.2020.e03843
  • F. Muhammad and L. Susilowati, “Algorithm and computer program to determine metric dimension of graph,” in Journal of Physics: Conference Series, Vol. 1494, No. 1, p. 012018, Mar. 2020, https://doi.org/10.1088/1742-6596/1494/1/012018
  • S. U. Rehman, M. Imran, and I. Javaid, “On the metric dimension of arithmetic graph of a composite number,” Symmetry, Vol. 12, No. 4, p. 607, Apr. 2020, https://doi.org/10.3390/sym12040607
  • M. Feng, X. Ma, and K. Wang, “The structure and metric dimension of the power graph of a finite group,” European Journal of Combinatorics, Vol. 43, pp. 82–97, Jan. 2015, https://doi.org/10.1016/j.ejc.2014.08.019
  • S. B. Pejman, S. Payrovi, and A. Behtoei, “Metric dimension of Andrásfai graphs,” Opuscula Mathematica, Vol. 39, No. 3, pp. 415–423, Jan. 2019, https://doi.org/10.7494/opmath.2019.39.3.415
  • G. Ali, R. Laila, and M. Ali, “Metric dimension of some families of graph,” Mathematical Sciences Letters, Vol. 5, No. 1, pp. 99–102, Jan. 2016, https://doi.org/10.18576/msl/050114
  • A. Estrada-Moreno, I. G. Yero, and J. A. Rodríguez-Velázquez, “The k-metric dimension of corona product graphs,” Bulletin of the Malaysian Mathematical Sciences Society, Vol. 39, No. S1, pp. 135–156, Dec. 2015, https://doi.org/10.1007/s40840-015-0282-2
  • 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
  • B. Mohamed, “A comprehensive survey on the metric dimension problem of graphs and its types,” International Journal of Theoretical and Applied Mathematics, Vol. 9, No. 1, pp. 1–5, Jul. 2023, https://doi.org/10.11648/j.ijtam.20230901.11
  • 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
  • V. Saenpholphat and P. Zhang, “Connected resolvability of graphs,” Czechoslovak Mathematical Journal, Vol. 53, No. 4, pp. 827–840, Dec. 2003, https://doi.org/10.1023/b:cmaj.0000024524.43125.cd
  • L. Eroh, C. X. Kang, and E. Yi, “The connected metric dimension at a vertex of a graph,” Theoretical Computer Science, Vol. 806, pp. 53–69, Feb. 2020, https://doi.org/10.1016/j.tcs.2018.11.002
  • B. Mohamed and M. Amin, “A hybrid optimization algorithms for solving metric dimension problem,” International Journal on Applications of Graph Theory in Wireless Ad Hoc Networks and Sensor Networks, Vol. 15, No. 1/2, pp. 1–10, Jun. 2023, https://doi.org/10.5121/jgraphoc.2023.15201
  • B. Mohamed, L. Mohaisen, and M. Amin, “Computing connected resolvability of graphs using binary enhanced Harris Hawks optimization,” Intelligent Automation and Soft Computing, Vol. 36, No. 2, pp. 2349–2361, Jan. 2023, https://doi.org/10.32604/iasc.2023.032930
  • B. Mohamed, L. Mohaisen, and M. Amin, “Binary equilibrium optimization algorithm for computing connected domination metric dimension problem,” Scientific Programming, Vol. 2022, No. 4, pp. 1–15, Oct. 2022, https://doi.org/10.1155/2022/6076369
  • B. Mohamed, “Metric dimension of graphs and its application to robotic navigation,” International Journal of Computer Applications, Vol. 184, No. 15, pp. 1–3, Jun. 2022, https://doi.org/10.5120/ijca2022922090
  • M. Faheem, Z. Zahid, D. Alrowaili, I. Siddique, and A. Iampan, “Fault-tolerant resolvability in some classes of subdivision graphs,” Journal of Mathematics, Vol. 2022, pp. 1–15, Feb. 2022, https://doi.org/10.1155/2022/5784800
  • D. Alrowaili, Z. Zahid, I. Siddique, S. Zafar, M. Ahsan, and M. S. Sindhu, “On the constant edge resolvability of some unicyclic and multicyclic graphs,” Journal of Mathematics, Vol. 2022, pp. 1–9, Jul. 2022, https://doi.org/10.1155/2022/6738129
  • M. Ahmad, F. Jarad, Z. Zahid, and I. Siddique, “Minimal doubly resolving sets of certain families of toeplitz graph,” Computer Modeling in Engineering and Sciences, Vol. 135, No. 3, pp. 2681–2696, Jan. 2023, https://doi.org/10.32604/cmes.2023.022819
  • L. Colton, C. Glover, M. Hughes, and S. Sandberg, “A Reidemeister type theorem for petal diagrams of knots,” Topology and its Applications, Vol. 267, p. 106896, Nov. 2019, https://doi.org/10.1016/j.topol.2019.106896
  • 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
  • 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, pp. 65–74, Jun. 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

Received
27 April 2024
Accepted
21 June 2024
Published
31 July 2024
Keywords
distance
metric dimension
resolving set
connected metric dimension
Acknowledgements

The authors have not disclosed any funding.

Data Availability

The datasets generated during and/or analyzed during the current study are available from the corresponding author on reasonable request.

Author Contributions

Iqbal M. Batiha: conceptualization, data curation. Nidal Anakira: resources, funding, supervision. Amal Hashim: software, investigation, formal analysis. Basma Mohamed: methodology, visualization, validation.

Conflict of interest

The authors declare that they have no conflict of interest.