Published: 21 April 2024

Connected metric dimension of the class of ladder graphs

M. Iqbal Batiha1
Mohamed Amin2
Basma Mohamed3
H. Iqbal Jebril4
1Nonlinear Dynamics Research Center (NDRC), Ajman University, Ajman 346, United Arab Emirates
1, 4Department of Mathematics, Al Zaytoonah University of Jordan, Amman 11733, Jordan
2, 3Mathematics and Computer Science Department, Faculty of Science, Menoufia University, Shebin El-Koom, Egypt
Corresponding Author:
M. Iqbal Batiha
Article in Press
Views 15
Reads 10
Downloads 34

Abstract

Numerous applications, like robot navigation, network verification and discovery, geographical routing protocols, and combinatorial optimization, make use of the metric dimension and connected metric dimension of graphs. In this work, the connected metric dimension types of ladder graphs, namely, ladder, circular, open, and triangular ladder graphs, as well as open diagonal and slanting ladder graphs, are studied.

Highlights

  • Recognizing numerous applications of the connected metric dimension types, including robot navigation, network verification and discovery, geographical routing protocols, and combinatorial optimization.
  • Making use of the metric dimension and connected metric dimension of graphs.
  • Studying the connected metric dimension types of ladder graphs, namely, ladder, circular, open, and triangular ladder graphs, as well as open diagonal and slanting ladder graphs.

1. Introduction

In [1, 2], a connected resolving set of graphs was introduced recently. The shortest path between any two vertices u,vV(G) in a linked graph G=(V, E) is represented by d(u, v). An ordered vertex set B={x1,x2,...,xk} V(G) is a metric basis of G if B has minimum cardinality and the following representation:

1
r(v| B)=(d(v,x1), d(v,x2),,d(v, xk)),

is unique for each vV(G). A metric basis B of G is connected if the subgraph B - produced by B is a nontrivial connected subgraph of G. The metric dimension and connected metric dimension of G, denoted as dim(G) and cdim(G), respectively, have the following definitions: Let |B| be the cardinality of B, then we have: dim(G)=min {|Bi|: Bi 2v, Bi is a resolving set of G}, cdim(G)=min {|Bi|:Bi 2v, Bi is a connected resolving set of G}.

The connected metric dimension at a vertex vV(G), denoted as cdimG(v), is the metric basis of G that contains v and generates a connected subgraph of G; then:

2
cdimG=minvV GcdimGv.

Slater [3, 4] introduced the concept of metric basis as a locating set of G and uses the cardinality of B as a locating number to locate an intruder in a network. Harary and Melter independently discovered the ideas of a metric basis as a minimum resolving set of G and the cardinality of B as a metric dimension [5]. A number of graphs’ metric dimensions are found in [6–15]. The following are the graphs: corona product [6], regular bipartite [7], chain graphs [8], mobius ladder [9], circulant graphs and Cayley hypergraphs [10], heptagonal circular ladder [11], generalized Petersen multigraphs [12], power of total graph [13], friendship graph [14], and quartz graph [15]. Specifically, the authors in [1] studied the linked metric dimension of the n-1 star network K1, full graph Kn, cycle graph Cn, route graph Pn, and wheel graph Wn. The findings show that the cycle graph Cn, n3, and the route graph Pn, n2, both have connected metric dimensions that are equal to 2, whereas it is for the star graph K1,n-1, n4, is n-1, and for the complete graph Kn, n3, is n-1. According to [2], the connected metric dimension of the wheel graph Wn, n7, is 2n+25+1, while it is for the Petersen graph P is 4, and if v is an end vertex of the tree T, then it is at a vertex of T; otherwise, it is at a vertex of T that is 2. Further information might be found in the literature [16-22], and some future notions may be applied to some applications like [23, 24].

To illustrate the ideas of metric dimension with its connected one, we plot in Fig. 1 the 3C4 –snake graph.

Fig. 13C4-Snake graph G with dim⁡G=3 and cdim⁡G=5

3C4-Snake graph G with dim⁡G=3 and cdim⁡G=5

The set B= v1,v5,v8 is a metric basis of G, due to the representations for the vertices of G are distinct. Since the representations rv1B=0,2,3, rv2B=1,3,4, rv3B=2,2,3, rv4B=1,1,2, rv5B=2,0,3, rv6B=3,1,2, rv7B=2,2,1, rv8B=3,3,0, rv9B=4,4,1, r(v10|B)=(3,3,2) for the vertices of G are different, the set B={v1, v5, v8} is a metric basis of G. Therefore, dim(G)=3, and the subgraph induced by B-=(B,E) is disconnected. As a result, B and G are not connected resolving sets. To be more precise, no 3-element subset of G is a connected resolving set. Given that the representations rv1B-=0,1,2,2,3, rv2B-=1,2,3,3,4, rv3B-= 2,1,2,2,3, rv4B-=1,0,1,1,2, rv5B-=2,1,0,2,3, rv6B-=3,2,1,1,2, rv7B-=2,1,2,0,1, rv8B-=3,2,3,1,0, rv9B-=4,3,4,2,1, r(v10|B-) =(3,2,3,1,2) are distinct, the set B-={v1,v4,v5,v7,v8} is a connected resolving set. Therefore, cdim(G)=5. However, we aim in this article to examine the connected metric dimension of a class of ladder graphs that includes slanting, open diagonal, triangular, open, circular, and open ladder graphs.

2. Applications of ladder graph

We present three applications pertaining to ladder graphs in this section. The three uses listed above and many more inspire us to study the uniquely elegant labelling for the ladder graph. The first application that is filed is in electronics. Resistor ladder networks are a quick and inexpensive way to do digital-to-analog conversion (DAC). The binary weighted ladder and the R/2R ladder are the two most widely used networks. Both devices can convert digital voltage information to analogue, but due to its greater accuracy and simple construction, the R/2R ladder has gained more popularity. The second application is electrical technology. The ladder flow graph is made using Ohm's equation and the two Kirchhoff equations. After that, the graph is inverted so that only forward paths are visible. The reciprocal of the total number of paths that could possibly lead from the output to the input node is the transfer function in the case of a simple ladder. If ladders with internal generators are dependent or independent, the transfer function can be found using similar methods with slight adjustments. Other relations, such as the input impedance and transfer admittance, can also be found using the flow graph. The third application is wireless communication. Over time, an increasing number of wireless networks have been developed to provide wire-free communication between any two devices (computers, phones, etc.). Nevertheless, there aren’t enough radio frequencies accessible for wireless communication (just 11 channels in the 2.4 GHz range are available for all WiFi transmissions in the US). It is essential to provide a workable manner to offer safe communications in industries like phones, mobile, security systems, WiFi, and many others [25]. It annoys me when someone else calls while I’m on the phone. This irritation is caused by interference from uncontrolled simultaneous transmissions [26]. Resonance or interference between two sufficiently adjacent channels can cause damage to communication. Interference can be prevented with the proper channel assignment. To arrive at a solution, Hale [27-30] conceptualized the problem as a graph (vertex) coloring model, which we now refer to as the L(2,1) coloring. Consider about the different transmitters and stations that are out there. In order to minimize interference, a channel must be assigned to each transmitter or station. Time-sensitive or error-sensitive communication may suffer from the interference phenomenon if transmitters are placed too close to one another either physically or through the frequency channels they use. To minimize interference, any two “close” transmitters ought to differ as much as possible from one another.

3. Results

Note that the two paths P2 and Pn are the Cartesian products of a ladder graph Ln.

Theorem 3.1. We have cdimLn=n2, n 4.

Fig. 2Ladder graph Ln

Ladder graph Ln

Proof. Herein, we select B- as B-=v1,v2,,vn-22,vn2. In this regard, we shall study each of the vertex representations of viV Ln such that n=2k+2 for n4 with respect to B-. In other words, we have:

3
r(vi|B-)=0,1,2,,,k, i=1,i-1,i-2, ,0,1,,k-i+1 ,2ik,i-1,i-2, ,1,0,i=k+1,1, 2, 3, ,k+1,i=k+2,(i-k-1,i-k-2, ,1,2,,n-i+1),k+3in-1,(k+1,k,k-1,,2,1),i=n.

The set B-= v1,v2,..,vn-22,vn2 has an induced subgraph that is connected, and as previously demonstrated, the vertices in graph Ln have unique representations. Despite not always being the lowest limit, this implies that B- is a connected resolving set. Therefore, cdim(Ln)n2 is an upper bound. Thus, cdim(Ln)n2 is demonstrated. Given a connected resolving set B-= v1,v2,,vn-22,vn2, we assume that B-=n2, and B-1 is another minimum connected resolving set.

In the case that we choose an ordered set:

4
B-1B-- vi, vj, 1 i, j n2, i j,

for which the two vertices vi, vjLn are exist so that:

5
r(vi|B-)=r(vj|B-)=n-22,n-22-1,n-22-2, ..., 1.

This is not the case; B-1 is not a connected resolving set as assumed. The lowest bound is therefore cdim (Ln)n2.

Corollary 3.2. If the ladder graph (C(Ln), n4, n=2k+2, is circular, then:

6
cdim(C(Ln)) =n-k-12,k is odd,n-k2,k is even.

Fig. 3Circular Ladder graph C(Ln)

Circular Ladder graph C(Ln)

Theorem 3.3. If the ladder graph O(Ln), n8 is open, then cdimOLn=n2.

Fig. 4Open ladder graph OLn

Open ladder graph OLn

Proof. Consider we have B-=v1,v2,,vn-22,vn2. With respect to B-, we take into consideration the following representations of vertices v1VO Ln, n8, n=2k+6. So, we have:

7
r(vi|B-)=0,1,2,,k+2, i=1,i-1,i-2, ,0,1,,k-i+2,k-i+3 ,2ik+2,i-1,i-2, ,1,0,i=k+3,3, 2, 3, ,k+3,i=k+4,(i-2k+1,i-2k, ,1,2,,n-i+1),k+5 i n-1,(k+2, k+1, k, k-1, ,3,2,3),i=n.

Although the induced subgraph of B- is clearly connected and the representations of the vertices in graph OLn are different, this does not necessarily imply that B- is a connected resolving set. For this reason, cdim(O Ln)n2 is an upper bound.

We now demonstrate that cdim(O Ln)n2. Given a connected resolving set B-= v1,v2,,vn-22,vn2 with |B-|=n2. Let B-1 be an additional minimal connected resolving set. Let us choose an ordered set:

8
B-1B--vi,vj, 1 i, jn2, ij,

for which there are two vertices vi, vjOLn such that:

9
r(vi|B-)=r(vj|B-)=n2-1, n2-2, n2-3, , 1.

It is not the case that B-1 is a connected resolving set, as implied. Thus, cdim(O Ln)n2 is the lower bound. Ultimately, cdimO Ln=n2.

Theorem 3.4. For n4, cdim(TLn)=n2 for which G is a triangular ladder graph TLn.

Fig. 5Triangular Ladder graph TLn

Triangular Ladder graph TLn

Proof. For n4 such that n=2k+2, we take into consideration a connected resolving set of (TLn) as the set B-=v1,v2,,vn-22,vn2. The vertices’ representations viV(TLn) in connection to B- are given as follows:

10
r(vi|B-)=0,1,2,,k, i=1,i-1,i-2, ,0,1,,k-i,k-i+1 ,2ik,k,k-1, ,1,0,i=k+1,1, 2, ,k ,k+1,i=k+2,(i-n+k ,i-n+k-1, ,1,1,2,,n-i+1),k+3in.

The unique vertex representations in graph TLn suggest that B- is a connected resolving set, and as can be seen above, the induced subgraph of B- is indeed connected, but this is not always the case. Therefore, cdim(TLn)n2 is an upper bound. Thus, we demonstrate that cdim(TLn)n2.

Given a connected resolving set B-=v1,v2,,vn-22,vn2, |B-| =n2. Let B-1 be an additional minimal connected resolving set. When we choose an ordered set:

11
B-1B--vi,vj, 1 i, jn2, ij.

Obviously, we can see that vi, vjTLn for which:

12
r(vi|B-)=r(vj|B-)=n-22,n-22-1, n-22-2, ,1.

It is not the case that B-1 is a connected resolving set, as implied. Hence, the lower bound is cdim (TLn)n2. Therefore, we have cdim TLn=n2.

Corollary 3.5. For an open triangular ladder O(TLn), we have cdimOTLn=3, n8.

Fig. 6Open triangular Ladder O(TLn)

Open triangular Ladder O(TLn)

Theorem 3.6. If SLn is a Slanting ladder graph, then cdim(SLn)=n2, for n 6.

Fig. 7Slanting Ladder SLn

Slanting Ladder SLn

Proof. By taking into consideration viV(SLn) with respect to B-, we assume that B-= v1,v2,,vn-22,vn2 is a connected resolving set for (SLn) in which n6, n=2k+4. This implies:

13
r(vi|B-)=0,1,2,,k+1, i=1,i-1,i-2, ,0,1,,k-i+2 ,2ik+2,2,3, ,k+3,i=k+3,1, 2, ,k+2,i=k+4,(i-2k+1,i-2k, ,1,2,n-i+2),k+5in.

The unique vertex representations in graph SLn suggest that B- is a connected resolving set, and as can be shown above, the induced subgraph of B- is clearly connected, but this is not always the case we desire. Because of this, cdim(SLn)n2 is an upper bound. Thus, we demonstrate that cdim(SLn)n2.

Given a connected resolving set B-=v1,v2,..,vn-22,vn2, with |B-|=n2. Let B-1 be an additional minimal connected resolving set. In the event that we choose the following ordered set:

14
B-1B--vi,vj, 1 i, jn2, ij,

for which vi, vjSLn satisfying:

15
r(vi|B-)=r(vj|B-)=n-22,n-22-1, n-22-2, ,1.

It will not be a connected resolving set if, in contrast to the assumption, we choose an ordered B-1. As a consequence, the lower bound is cdim(SLn)n2, and hence cdimSLn=n2.

Theorem 3.7. If the graph O(DLn) is an open diagonal ladder, then cdim(O(DLn))=n2, n6.

Proof. Take into consideration the connected resolving set of (O(DLn)) for which n6, n=2k+6, and the set B-=v1,v2,,vn-22,vn2. With respect to B-, consider viV(O(DLn)) as follows:

16
r(vi|B-)=0,1,2,,k+2, i=1,i-1,i-2, ,0,1,,2k-i-2,2k-i-1 ,2ik+2,i-1,i-2, ,1,0,i=k+3,i-2, i-3,,1 ,2,i=k+4,(n-i,n-i-1, ,1,1,1,i-2k),k+5in-1,(2, 1, 2,3, ,k+2),i=n.

In graph O(DLn), the vertex representations are unique and the induced subgraph of B- is undoubtedly connected, as can be observed above. This suggests that B- is a connected resolving set, though it need not be the lowest bound. For this reason, cdim(O(DLn)) n2 is an upper bound, and thus we demonstrate that cdim(O(DLn))n2.

Fig. 8Open diagonal ladder graph O(DLn)

Open diagonal ladder graph O(DLn)

Given a connected resolving set B-=v1,v2,,vn-22,vn2 with |B-|=n2. Let B-1 be an extra minimal connected resolving set. Assume that we choose the following ordered set:

17
B-1B--vi,vj, 1 i, jn2, ij,

for which vi, vjO(DLn) satisfying:

18
r(vi|B-)=r(vj|B-)=n-22,n-22-1, n-22-2, , 1.

It will not be a connected resolving set if, in contrast to the assumption, we choose an ordered B-1. As a consequence, the lower bound is cdim(O(DLn) )n2, and hence cdimO(DLn) =n2.

4. Conclusions

The constant metric dimension of an open triangular ladder O(TLn) is 3. There are several types of ladder graphs with unbounded metric dimensions as n, circular, open, triangular, slanting, and open diagonal. Our approach will be extended to ladder-class graph subdivisions in the future.

References

  • 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
  • P. J. Slater, “Leaves of trees,” Congressus Numerantium, Vol. 14, pp. 549–559, 1975.
  • P. J. Slater, “Dominating and reference sets in a graph,” Journal of Mathematical Physics, Vol. 22, No. 4, pp. 445–455, 1988.
  • F. Harary and R. A. Melter, “On the metric dimension of a graph,” Ars Combinatoria, Vol. 2, pp. 191–195, 1976.
  • I. G. Yero, D. Kuziak, and J. A. Rodríguez-Velázquez, “On the metric dimension of corona product graphs,” Computers and Mathematics with Applications, Vol. 61, No. 9, pp. 2793–2798, May 2011, https://doi.org/10.1016/j.camwa.2011.03.046
  • S. W. Saputro, E. T. Baskoro, A. N. M. Salman, D. Suprijanto, and M. Baca, “The metric dimension of regular bipartite graphs,” Bulletin mathématique de la Société des Sciences Mathématiques de Roumanie, pp. 15–28, Jan. 2011.
  • H. Fernau, P. Heggernes, P. van T. Hof, D. Meister, and R. Saei, “Computing the metric dimension for chain graphs,” Information Processing Letters, Vol. 115, No. 9, pp. 671–676, Sep. 2015, https://doi.org/10.1016/j.ipl.2015.04.006
  • Mobeen Munir, “Metric dimension of the mobius ladder,” Ars Combinatoria, Vol. 135, pp. 249–256, Jan. 2017.
  • A. Borchert and S. Gosselin, “The metric dimension of circulant graphs and Cayley hypergraphs,” Utilitas Mathematica, Vol. 106, pp. 125–147, Mar. 2018.
  • S. K. Sharma and V. K. Bhat, “Metric dimension of heptagonal circular ladder,” Discrete Mathematics, Algorithms and Applications, Vol. 13, No. 1, p. 2050095, Aug. 2020, https://doi.org/10.1142/s1793830920500950
  • M. Imran, M. K. Siddiqui, and R. Naeem, “On the metric dimension of generalized Petersen multigraphs,” IEEE Access, Vol. 6, pp. 74328–74338, Jan. 2018, https://doi.org/10.1109/access.2018.2883556
  • S. Nawaz, M. Ali, M. A. Khan, and S. Khan, “Computing metric dimension of power of total graph,” IEEE Access, Vol. 9, pp. 74550–74561, Jan. 2021, https://doi.org/10.1109/access.2021.3072554
  • M. Mulyono and W. Wulandari, “The metric dimension of friendship graph Fn, lollipop graph Lm,n and Petersen graph Pn, m,” Bulletin of Mathematics, Vol. 8, No. 2, pp. 117–124, 2016.
  • A. N. A. Koam, A. Ahmad, M. S. Alatawi, M. F. Nadeem, and M. Azeem, “Computation of metric-based resolvability of quartz without pendant nodes,” IEEE Access, Vol. 9, pp. 151834–151840, Jan. 2021, https://doi.org/10.1109/access.2021.3126455
  • 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, pp. 1–15, Oct. 2022, https://doi.org/10.1155/2022/6076369
  • I. M. Batiha, A. A. Abubaker, I. H. Jebril, S. B. Al-Shaikh, and K. Matarneh, “New algorithms for dealing with fractional initial value problems,” Axioms, Vol. 12, No. 5, p. 488, May 2023, https://doi.org/10.3390/axioms12050488
  • 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
  • S. Klavžar and D. Kuziak, “Nonlocal metric dimension of graphs,” Bulletin of the Malaysian Mathematical Sciences Society, Vol. 46, No. 2, pp. 1–14, Jan. 2023, https://doi.org/10.1007/s40840-022-01459-x
  • A. N. A. Koam, A. Ahmad, S. Husain, and M. Azeem, “Mixed metric dimension of hollow coronoid structure,” Ain Shams Engineering Journal, Vol. 14, No. 7, p. 102000, Jul. 2023, https://doi.org/10.1016/j.asej.2022.102000
  • C. Zhang, G. Haidar, M. U. I. Khan, F. Yousafzai, K. Hila, and A. U. I. Khan, “Constant time calculation of the metric dimension of the join of path graphs,” Symmetry, Vol. 15, No. 3, p. 708, Mar. 2023, https://doi.org/10.3390/sym15030708
  • A. Goldsmith, Wireless Communications. Cambridge University Press, 2005, https://doi.org/10.1017/cbo9780511841224
  • 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
  • Iqbal 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.
  • R. Wakefield, Radio Broadcasting. 1959.
  • W. K. Hale, “Frequency assignment: theory and applications,” Proceedings of the IEEE, Vol. 68, No. 12, pp. 1497–1514, Jan. 1980, https://doi.org/10.1109/proc.1980.11899
  • A. R. Kannan, P. Manivannan, K. Loganathan, K. Prabu, and S. Gyeltshen, “Assignment computations based on average in various ladder graphs,” Journal of Mathematics, Vol. 2022, pp. 1–8, May 2022, https://doi.org/10.1155/2022/2635564
  • I. Saifudin, H. Oktavianto, and L. A. Muharom, “The four-distance domination number in the ladder and star graphs amalgamation result and applications,” JTAM (Jurnal Teori dan Aplikasi Matematika), Vol. 6, No. 2, pp. 235–246, Apr. 2022, https://doi.org/10.31764/jtam.v6i2.6628
  • H. Al-Zoubi, A. K. Akbay, T. Hamadneh, and M. Al-Sabbagh, “Classification of surfaces of coordinate finite type in the Lorentz-Minkowski 3-space,” Axioms, Vol. 11, No. 7, p. 326, Jul. 2022, https://doi.org/10.3390/axioms11070326

About this article

Received
15 January 2024
Accepted
14 March 2024
Published
21 April 2024
Keywords
connected metric dimension
ladder graphs
connected resolving set
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

M. Iqbal Batiha: conceptualization, validation, data curation. Mohamed Amin: methodology, formal analysis, supervision. Basma Mohamed: software, investigation. Iqbal H. Jebril: resources, visualization, supervision.

Conflict of interest

The authors declare that they have no conflict of interest.