# On Metric Dimension of Subdivided Honeycomb Network and Aztec Diamond Network

Authors: Xiujun Zhang; Hafiz Muhammad Bilal; Atiq ur Rehman; Muhammad Hussain; Zhiqiang Zhang
Journal: Discrete Dynamics in Nature and Society
 (2023)

---

## Abstract

This paper investigates the metric dimensions of the polygonal networks, particularly, the subdivided honeycomb network, Aztec diamond as well as the subdivided Aztec diamond network. A polygon is any two-dimensional shape formed by straight lines. Triangles, quadrilaterals, pentagons, and hexagons are all representations of polygons. For instance, hexagons help us in many models to construct honeycomb network, wheren is the number of hexagons from a central point to the borderline of the network. A subdivided honeycomb network SHCNn is obtained by adding additional vertices on each edge of HCNn. An Aztec diamond network AZNn of order n is a lattice comprises of unit squares with center a,b satisfying a+b≤n. The subdivided Aztec diamond network SAZNn is obtained by adding additional vertices to each edge of AZNn. In this work, our main aim is to establish the results to show that the metric dimensions of SHCNn and AZNn are 2 and 3 for n=1 and n≥2, respectively. In the end, some open problems are listed with regard to metric dimensions for k-subdivisions of HCNn and AZNn.


---

## Body

## 1. Introduction

Graph theory is used as an important mean for modeling real-world problems, including physicochemical property testing [1]. Inspired by the problem of evaluating the position of an individual across the defined network precisely, Slater [2] presented the concept of the metric dimension of a graph, where the metric generators are referred to as locating sets. Coming after Slater’s concept, Harary and Melter [3] extended the work on metric dimension by defining metric generators as resolving sets. It has many applications in different fields of life, for example, image processing, network theory, pattern recognition, optimization, and robot navigation. Throughout the graph, a traveling point can be identified after measuring the length between the point and sound stations that have been precisely located in the graph.The mathematical illustration of various chemical structures is of vital importance for the chemists to discover drugs. A labeled graph is used to describe the composition of a chemical compound, edges indicate atomic bonds and vertices represent atoms [4, 5]. In a navigation network, a robot that needs to find its current position during navigation in space is modeled by a graph. It may send signals in order to measure its distance from each of a set of defined destinations. Here, the problem is to measure the minimum number of destinations with their locations, as the robots can likely decide their positions. The set of nodes representing destinations and the number of destinations are known as the metric basis and the metric dimension of the graph, respectively.The metric dimension is formally initiated after considering a connected graphG=V,E, carrying set V of vertices/nodes and set E of edges. Let v1,v2∈V be two distinct vertices, then the length of the shortest v1v2-path denotes the distance for them that is symbolized by dv1,v2. A set Nkv=udu,v=k is the k-neighborhood of vertex v∈V, where k is a positive integer. If M=m1,m2,…,mk is the ordered subset of vertices and v∈G, then rvM=dv,m1,dv,m2,…,dv,mk is called the code of v in relation with M. If there exist separate codes for two vertices in G, then M is the resolving set [3] (or locating set [6]) for G. The minimum cardinality of a resolving (or locating) set refers as metric dimension of G symbolized by dimG. While a locating (or resolving) set with a minimum number of vertices is called basis for G [7].Raj et al. studied metric dimensions of different chemical networks as well as star of David networkSDNn in [8, 9]. If the vertices of a connected graph are changed, then the metric dimension of the graph will also be changed and become infinite when the number of vertices is infinite; this is called an unbounded metric dimension. Similarly, the metric dimension remains finite when changes in the number of vertices is finite and is called bounded metric dimension. Finally, if the metric dimension remains the same as the number of all vertices in a connected graph G, then it is called a constant metric dimension [10]. The metric dimension of a path graph is 1 in [5]; cycles have a metric dimension 2 for every n≥3. The rooted product of two graphs F and J is stated as follows: take u=VF copies of J, and for each vertex uj of F, identify ui with the root node of the jth copy of J. Godsil and McKay [11], the rooted product of Harary graphs Hm,n, Jahangir graphs, antiprism An, and generalized Petersen graphs Pn,2 by path and cycle would be calculated as well as metric dimensions of line graph of certain families of graphs would be determined. It is also of interest to determine the rooted product of graphs and then find out the metric dimension of the rooted product of graphs by path and cycle. Imran et al. [12] have established some results of the metric dimension for some gear graphs. Manuel et al. [13] determined the constant metric dimension of honeycomb networks. Moreover, in [14–16], we determined the metric dimensions and edge metric dimensions for honeycomb, hex-derived, and hexagonal networks. Zahid et al. determined the edge metric dimension of the wheel graph, k multiwheel graph, and Cayley graphs and its barycentric subdivisions in [17–19]. After gaining some idea of Manuel, the metric dimension of the subdivided honeycomb network would be determined.


## 2. Honeycomb Network

In this section, firstly, the structural introduction ofHCNn [13] and SHCNn is given. Secondly, we have established some results and showed that the metric dimensions of SHCNn for n=1 and n≥2 are 2 and 3, respectively.There is a range of designs in which polygons play a role to construct a honeycomb networkHCNn, where n denotes the number of hexagons from the center to the boundary of the network. Given HCN1, we will have to add a layer of six hexagons to the exterior boundary of HCN1 in order to construct HCN2. Consequently, after coating HCNn−1 with 6n−1 hexagons, we get HCNn. While SHCNn is obtained by adding additional vertices to each edge of HCNn. The honeycomb network is very useful in navigation, computer graphics, image processing, and cell phone.The diagrams in Fig(1) are examples of SHCN2 with 1 subdivision.Figure 1
HoneycombHCN2 and subdivided honeycomb network SHCN2 with 1 subdivision.Theorem 1.
IfG≅SHCN1, then the metric dimension of G is 2.Proof.
SHC1 is a cycle with 12 vertices; it is not a path so its metric dimension is not 1 [4], and as it is C12, it has metric dimension 2.Theorem 2.
IfG≅SHCNn, then G has a metric dimension greater than 2 for n≥2.Proof.
Here, we have to show thatG does not have any resolving set M with two vertices. On the contrary, suppose that G has metric dimension equal to 2.
ForM=a1,ai, it implies that rviM=ruiM. Hence, M is not a resolving set for the graph.
ForM=v1,v8n−3, it implies that rci1M=rui+2M. Hence, M is not a resolving set.
ForM=d1i,di1, it implies that rti1M=rui+2M. Hence, M is not a resolving set.
ForM=c1j,cij, it implies that rt3jM=rt7jM. Hence, M is not a resolving set.
ForM=u1,u8n−3, it implies that rti1M=rvi+2M. Hence, M is not a resolving set.
ForM=t1j,tij, it implies that rc3jM=rc7jM. Hence, M is not a resolving set.
ForM=v1,u1, it implies that rd11M=ru4M. Hence, M is not a resolving set.
ForM=v1,a1, it implies that ra11,M=rv4M. Hence, M is not a resolving set.
ForM=u1,a1, it implies that rd11M=ru4M. Hence, M is not a resolving set.
ForM=v1,c11, it implies that ru5M=rv7M. Hence, M is not a resolving set.
ForM=u1,c11, it implies that ru12M=rt81M. Hence, M is not a resolving set.
Therefore, with two vertices, there is no resolving setM for SHCNn, n≥2, so its metric dimension is greater than 2.Theorem 3.
IfG≅SHCNn, n≥2, then the metric dimension of G is 3.Proof.
TheSHCNn with one vertex between every two vertices has a vertex set,(1)VSHCNn=vi:1≤i≤8n−3∪ai:1≤i≤2n∪aij:1≤i≤2n−j+1,1≤j≤n−1∪dij:1≤i≤2n−j+1,1≤j≤n−1∪cij:1≤i≤8n−4j−3,1≤j≤n−1∪ui:1≤i≤8n−3∪tij:1≤i≤8n−4j−3,1≤j≤n−1.
Now, letM=v1,u1,v8n−3 be the resolving set for the above graph.(2)rviM=i−1,i+1,8n−i−3,1≤i≤8n−3,raiM=4i−3,4i−3,8n−4i+1,1≤i≤2n,raijM=4i+j−5,4i+j−3,8n−4i−1,1≤i≤2n−j+1,1≤j≤n−1,rdijM=4i+j−3,4i+j−5,8n−4i+1,1≤i≤2n−j+1,1≤j≤n−1,rcijM=4j+i−1,4j+i+1,8n−i−3,1≤i≤8n−4j−3,1≤j≤n−1,rcijM=4j+i−1,4j+i+1,8n−i−3,1≤i≤8n−4j−3,1≤j≤n−1,ruiM=i+1,i−1,8n−i−1,1≤i≤8n−3,rtijM=4j+i+1,4j+i−1,8n−i−1,1≤i≤8n−4j−3,1≤j≤n−1.
Letvl and vp be two distinct vertices from VSHCNn, then rvlM=rvpM⇒l−1,l+1,8n−l−3=p−1,p+1,8n−p−3⇒l=p, l=p, l=p which is contradiction.
Letalj and apj be two distinct vertices from VSHCNn, then raljM=rapjM⇒4l+j−5,4l+j−3,8n−4l−1=4p+j−5,4p+j−3,8n−4p−1⇒l=p, l=p, l=p which is contradiction.
Letdlj and dpj be two distinct vertices from VSHCNn, then rdljM=rdpjM⇒4l+j−3,4l+j−5,8n−4l+1=4p+j−3,4p+j−5,8n−4p+1⇒l=p, l=p, l=p which is contradiction.
Letul and up be two distinct vertices from VSHCNn, then rulM=rupM⇒l+1,l−1,8n−l−1=p+1,p−1,8n−p−1⇒l=p, l=p, l=p which is contradiction.
Similarly, now that we will consider two different vertices from opposite sides, we will again get contradiction.
Letvl and ap be two distinct vertices from VSHCNn, then rvlM=rapM⇒l−1,l+1,8n−l−3=4p−3,4p−3,8n−4p+1⇒l=22p−1,l=4p−1,l=4p−1 which is contradiction.
Letvl and apj be two distinct vertices from VSHCNn, then rvlM=rapjM⇒l−1,l+1,8n−l−3=4p+j−5,4p+j−3,8n−4p−1⇒l=4p+j−1,l=4p+j−1,l=22p−1 which is contradiction.
Letvl and cpj be two distinct vertices from VSHCNn, then rvlM=rcpjM⇒l−1,l+1,8n−l−3=4j+p−1,4j+p+1,8n−p−3⇒l=4j+p,l=4j+p,l=p which is contradiction.
Letalj and dpj be two distinct vertices from VSHCNn, then raljM=rdpjM⇒4j+l−5,4j+l−3,8n−4l−1=4p+j−3,4p+j−5,8n−4p+1⇒l=4p+2/4,l=4p−2/4,l=4p−2/4 which is contradiction.
Letalj and up be two distinct vertices from VSHCNn, then raljM=rupM⇒4j+l−5,4j+l−3,8n−4l−1=p+1,p−1,8n−p−1⇒l=p−4j+6/4,l=p−4j+2/4,l=p/4 which is contradiction.
Letalj and tpj be two distinct vertices from VSHCNn, then raljM=rtpjM⇒4j+l−5,4j+l−3,8n−4l−1=4j+p+1,4j+p−1,8n−p−1⇒l=p+6/4,l=p+2/4,l=p/4 which is contradiction.
Letdlj and cpj be two distinct vertices from VSHCNn, then rdljM=rcpjM⇒4j+l−3,4j+l−5,8n−4l+1=4j+p−1,4j+p+1,8n−p−3⇒l=p+2/4,l=p+6/4,l=p+4/4 which is contradiction.
Letclj and tpj be two distinct vertices from VSHCNn, then rcljM=rtpjM⇒4j+l−1,4j+l+1,8n−l−3=4j+p−1,4j+p+1,8n−p−1⇒l=p+2,l=p−2,l=p−2 which is contradiction.
If we consider the following options of two vertices and continue the process in this way, we will get contradiction,alj, tpj,clj, dpj,tlj, apj,ul, dpj,ul, tpj,ul, apj,vl, tpj,vl, dpj,clj, vp,alj, cpj,clj, vp,clj, and apj.
So, every vertex has distinct representation with respect toM, so M is a resolving set for SHCNn, n≥2.The following Figure2 represents the justification for the abovementioned Theorems 2 and 3.Figure 2
Structure of subdivided honeycomb networkSHCNn.


## 3. Aztec Diamond and Subdivided Aztec Diamond Network

In this section, firstly, the structural introduction ofAZNn is given. Secondly, we have established some results and showed that the metric dimensions of AZNn and SAZNn for n=1 and n≥2 are 2 and 3, respectively. The area derived from staircase shapes of height n when glued together by the straight edges is known as the Aztec diamond network AZNn [20] of order n. So, we can define it as a lattice comprises of unit squares centered at (a, b) such that a+b≤n. AZNn with order n is composed of 2nn+1 number of unit squares. An AZNn with different proportions is portrayed and further studied in [21, 22]. The diagrams in the following Figure 3 depict AZN1, AZN2, and AZN3, respectively. The subdivided Aztec diamond network SAZNn is obtained by adding additional vertices on each edge of AZNn.Figure 3
Structure of Aztec diamond networksAZN1, AZN2, and AZN3 (from left to right), respectively.Theorem 4.
IfG≅AZN1, then the metric dimension of G is 2.Proof.
AnAZNn has a vertex set(3)VAZn=vi:1≤i≤3∪ai:1≤i≤3∪ui:1≤i≤3.
Now, letM=v1,u1 be the resolving set for the abovementioned graph.(4)rviM=i−1,i+1,1≤i≤3,raiM=i,i,1≤i≤3,ruiM=i+1,i−1,1≤i≤3.
Letvl and vp be two distinct vertices from VAZNn, then rvlM=rvpM⇒l−1,l+1=p−1,p+1⇒l=p, l=p which is contradiction.
Letal and ap be two distinct vertices from VAZNn, then ralM=rapM⇒l,l=p,p⇒l=p, l=p which is contradiction.
Letul and up be two distinct vertices from VAZNn, then rulM=rupM⇒l+1,l−1=p+1,p−1⇒l=p, l=p which is contradiction.
Letvl and ap be two distinct vertices from VAZNn, then rvlM=rapM⇒l−1,l+1=p,p⇒l=p+1, l=p−1 which is contradiction.
Letvl and up be two distinct vertices from VAZNn, then rvlM=rupM⇒l−1,l+1=p+1,p−1⇒l=p+2, l=p−2 which is contradiction.
Letal and up be two distinct vertices from VAZNn, then ralM=rupM⇒l,l=p+1,p−1⇒l=p+1, l=p−1 which is contradiction.
Hence, every vertex has a distinct representation with respect toM, so M is a resolving set for AZNn and n=1.Theorem 5.
IfG≅AZNn, then G has a metric dimension greater than 2 for n≥2.Proof.
Suppose on contraryAZNn has D as its resolving set with cardinality 2. Let M=v1,v2n+1 be a resolving set. Here, rci1M=rai+1M,i=1,2,…,2n, which is contradiction.
LetM=u1,u2n+1 be a resolving set. Here, rpi1M=rai+1M,i=1,2,…,2n, which is contradiction.
LetM=ai,a2n+1 be a resolving set. Here, rviM=ruiD which is contradiction.
LetM=c1j,cij be a resolving set. Here, rv1M=ra2M which is contradiction.
LetM=p1j,pij be a resolving set. Here, ru1M=ra2M which is contradiction.
LetM=ui,v2n+1 be a resolving set. Here, rviM=rai+1M,i=1,2,…,2n, which is contradiction.
LetM=v2n+1,p1j be a resolving set. Here, rvi+1M=rai+2M which is contradiction.
LetM=u2n+1,c1j be a resolving set. Here, rui+1M=rai+2M,i=1,2,…,2n−1, which is contradiction.
LetM=a1,v2n+1 be a resolving set. Here, rviM=rai+1M,i=1,2,…,2n, which is contradiction.
LetM=a1,u2n+1 be a resolving set. Here, ruiM=rai+1M,i=1,2,…,2n, which is contradiction.
LetM=a1,c1j be a resolving set. Here, rviM=rai+1M,i=1,2,…,2n−1, which is contradiction.
LetM=a1,p1j be a resolving set. Here, ruiM=rai+1M,i=1,2,…,2n−1, which is contradiction.
Thus, there is no resolving set with two basis elements. It implies thatdimG>2 for n≥2.Theorem 6.
IfG≅AZNn, n≥2, then the metric dimension of G is 3.Proof.
TheAZNn has a vertex set(5)VAZn=vi:1≤i≤2n+1∪ui:1≤i≤2n+1∪ai:1≤i≤2n+1∪cij:1≤i≤2n−2j+1,1≤j≤n−1∪pij:1≤i≤2n−2j+1,1≤j≤n−1.
Now, letM=v1,u1,v2n+1 be the resolving set for the abovementioned graph.(6)rviM=i−1,i+1,2n−i+1,1≤i≤2n+1,ruiM=i+1,i−1,2n−i+3,1≤i≤2n+1,raiM=i,i,2n−i+2,1≤i≤2n+1,rcijM=2j+i−1,2j+i+1,2n−i+1,1≤i≤2n−2j+1,rpijM=2j+i+1,2j+i−1,2n−i+3,1≤i≤2n−2j+1.
Letvx and vy be two distinct vertices from VAZNn, then rvlM=rvpM⇒x−1,x+1,2n−x+1=y−1,y+1,2n−y+1⇒x=y, x=y, x=y which is contradiction.
Letcxj and cyj are two distinct vertices from VAZNn, then rcxjM=rcyjM⇒2j+x−1,2j+x+1,2n−x+1=2j+y−1,2j+y+1,2n−y+1⇒x=y, x=y, x=y which is contradiction.
Letpxj and pyj be two distinct vertices from VAZNn, then rpxjM=rpyjM⇒2j+x+1,2j+x−1,2n−i+3=2j+y+1,2j+y−1,2n−y+3⇒x=y, x=y, x=y which is contradiction.
Now, we will consider those vertices that are on opposite sides, as follows:
Letvx and uy be two distinct vertices from VAZNn, then rvxM=ruyM⇒x−1,x+1,2n−x+1=y+1,y−1,2n−y+3⇒x=y+2, x=y−2, x=y−2 which is contradiction.
Letvx and pyj be two distinct vertices from VAZNn, then rvxM=rpyjM⇒x−1,x+1,2n−x+1=2j+y+1,2j+y−1,2n−y+3⇒x=2j+y+2, x=2j+y−2, x=y−2 which is contradiction.
Letux and ay be two distinct vertices from VAZNn, then ruxM=rayM⇒x=1,x−1,2n−x+3=y,y,2n−y+2⇒x=y−1, x=y+1, x=y+1 which is contradiction.
Letux and cyj be two distinct vertices from VAZNn, then ruxM=rcyjM⇒x+1,x−1,2n−x+3=2j+y−1,2j+y+1,2n−y+1⇒x=2j+y−2, x=2j+y+2, x=y+2 which is contradiction.
Letcxj and pyj be two distinct vertices from VAZNn, then rcxjM=rpyjM⇒2j+x−1,2j+x+1,2n−x+1=2j+y+1,2j+y−1,2n−y+3⇒x=y+2, x=y−2, x=y−2 which is contradiction.
Under this process, by choosing any other options of two vertices we will get contradiction as mentioned above.
Hence, every vertex has a distinct representation with respect toM, so M is a resolving set for AZNn; n≥2.The following Figure4 represents the justification for Theorem 5 and Theorem 6.Figure 4
Aztec diamond AZN(n).Theorem 7.
IfG≅SAZNn, n≥2, then the metric dimension of G is 3.Proof.
TheSAZNn has a vertex set(7)VSAZn=vi:1≤i≤4n+1∪ui:1≤i≤4n+1∪ci:1≤i≤4n+1∪di:1≤i≤2n+1∪fi:1≤i≤2n+1∪aij:1≤i≤2n−2j+1and1≤j≤n−1∪bij:1≤i≤4n−4j+1∪gij:1≤i≤2n−2j+1and1≤j≤n−1∪hij:1≤i≤4n−4j+1and1≤j≤n−1.
Now, letM=v1,u1,v2n+1 be the resolving set for the abovementioned graph. Then,(8)rviM=i−1,i+3,4n−i+1,1≤i≤4n+1,ruiM=i+3,i−1,4n−i+5,1≤i≤4n+1,rciM=i+1,i+1,4n−i+3,1≤i≤4n+1,rdiM=2i−1,2i+1,4n−2i+3,1≤i≤2n+1,rfiM=2i+1,2i−1,4n−2i+5,1≤i≤2n+1,raijM=4j+i−1,4j+i+3,4n−i+1,1≤i≤2n−2j+1and1≤j≤n−1,rbijM=4j+2i−3,4j+2i+1,4n−2i+1,1≤i≤4n−4j+1and1≤j≤n−1,rgijM=4j+2i+1,4j+2i−3,4n−2i+5,1≤i≤2n−2j+1and1≤j≤n−1,rhijM=4j+i+3,4j+i−1,4n−i+5,1≤i≤4n−4j+1and1≤j≤n−1.
Letvl and vp be two distinct vertices from VSAZNn, then rvlM=rvpM⇒l−1,l+3,4n−l+1=p−1,p+3,4n−p+1⇒l=p, l=p, l=p which is contradiction.
Letcl and cp be two distinct vertices from VSAZNn, then rclM=rcpM⇒l+1,l+1,4n−l+3=p+1,p+1,4n−p+3⇒l=p, l=p, l=p which is contradiction.
Letalj and apj be two distinct vertices from VSAZNn, then raljM=rapjM⇒4j+l−1,4j+l+3,4n−l+1=4j+p−1,4j+p+3,4n−p+1⇒l=p, l=p, l=p which is contradiction.
Now, we will consider those vertices which are from opposite sides, as follow.
Letvl and up are two distinct vertices from VSAZNn, then rvlM=rupM⇒l−1,l+3,4n−l+1=p+3,p−1,4n−p+5⇒l=p+4, l=p−4, l=p−4 which is contradiction.
Letcl and apj be two distinct vertices from VSAZNn, then rclM=rapjM⇒l+1,l+1,4n−l+3=4j+p−1,4j+p+3,4n−p+1⇒l=4j+p−2, l=4j+p+2, l=p+2 which is contradiction.
Letfl and hpj be two distinct vertices from VSAZNn, then rflM=rhpjM⇒2l+1,2l+1,4n−2l+5=4j+p+3,4j+p−1,4n−p+5⇒l=4j+p+2/2, l=4j+p−2/2, l=p/2 which is contradiction.
Letblj and gpj be two distinct vertices from VSAZNn, then rbljM=rgpjM⇒4j+2l−3,4j+2l+1,4n−2l+1=4j+2p+1,4j+2p−3,4n−2p+5⇒l=p+2, l=p−2, l=p−2 which is contradiction.
Letalj and hpj be two distinct vertices from VSAZNn, then raljM=rhpjM⇒4j+l−1,4j+l+3,4n−l+1=4j+p+3,4j+p−1,4n−p+5⇒l=p+4, l=p−4, l=p−4 which is contradiction.
On continuing this process by choosing any other options of two vertices we will get contradiction as mentioned above.
Hence, every vertex has a distinct representation with respect toM, so M is a resolving set for SAZNn; n≥2.The following Figure5 represents the justification for the abovementioned Theorem 7.Figure 5
Subdivided SAZN(n).


## 4. Conclusions

In this paper, firstly, we investigated the structures ofHCNn, SHCNn, AZNn, and SAZNn. Then, we established the results and showed that the metric dimensions of SHCNn, AZNn, and SAZNn are 2 for n=1 and 3 for n≥2, respectively. We are raising the following problems for future perspective.Open Problem 1.
Determine the metric dimension of the subdivided honeycomb networkSHCNn for k subdivision.Open Problem 2.
Determine the metric dimension of the subdivided Aztec diamond networkSAZNn for k subdivision.



---

*Source: 7120232-2023-03-23.xml*