# Metric Dimension of Crystal Cubic Carbon Structure

Authors: Xiujun Zhang; Muhammad Naeem
Journal: Journal of Mathematics
 (2021)

---

## Abstract

For any given graphG, we say W⊆VG is a resolving set or resolves the graph G if every vertex of G is uniquely determined by its vector of distances to the vertices in W. The metric dimension of G is the minimum cardinality of all the resolving sets. The study of metric dimension of chemical structures is increasing in recent times and it has application about the topology of such structures. The carbon atoms can bond together in various ways, called allotropes of carbon, one of which is crystal cubic carbon structure CCCn. The aim of this article is to find the metric dimension of CCCn.


---

## Body

## 1. Introduction

LetG be a simple connected graph and let W=w1,w2,…,wk be an ordered subset of the set of vertices VG of G. The distance du,v of two vertices of G is the length of shortest path between u and v. The representation of a vertex u of G with respect to W is the k-vector du,w1,du,w2,…,du,wk and it is denoted as ru|W. The set W is called the resolving set or to resolve G if the representation of distinct vertices is distinct. That is, if u and v are two distinct vertices, then ru|W≠v|W. The metric dimension of a graph is the cardinality of the minimal resolving set and it is denoted as βG. As there may be many different resolving subsets in VG of different sizes, the study of the minimal one is important and it has been studied over the years. Some authors also use the term basis for G which is a resolving set with minimum cardinal number (see [1]). This work is about a study of resolving sets in chemical structural graphs.The metric dimension of a general metric space was introduced in 1953 in [2], but at that time, it attracted little attention. Then, about twenty years later, it was applied to the distances between vertices of a graph [3–5]. Since then, it has been frequently used in graph theory, chemistry, biology, robotics, and many other disciplines. For some literature studies, see [6–9].From many parameters for the study of graphs, the metric dimension is one of those that has many applications, and these applications are diverse like in pharmaceutical chemistry [10, 11], robot navigation [12], and combinatorial optimization [13]. A chemical compound or material can be represented by many graph structures, but only one of them may express its topological properties. The chemists require mathematical forms for a set of chemical compounds to give distinct representations to distinct compound structures. The structure of chemical compounds or materials can be represented by a labeled graph whose vertex and edge labels specify the atom and bond types, respectively. Thus, a graph theoretic interpretation of this problem is to provide representations for the vertices of a graph in such a way that distinct vertices have distinct representations.At very high pressures of above 1000 GPa (gigapascal), one of the forms of carbon, namely, diamond, is predicted to transform into the so-calledC8 structure, a body-centered cubic structure with 8 atoms in the unit cell. This cubic carbon phase might have importance in astrophysics. Its structure is known in one of the metastable phases of silicon and is similar to cubane. The structure of this phase was proposed in 2012 as carbon sodalite [14]. In 2017, Baig et al. [15] modified and extended this structure and named it crystal cubic carbon CCCn. We are taking all the notations as they were in [15]. The structure of crystal cubic carbon consists of cubes.The molecular graph of crystal cubic carbonCCCn for the second level is depicted in Figure 1. Its structure starts from one unit cube and then by attaching cubes at each vertex of the unit cube by an edge. For the third level, the CCC3 is constructed by attaching cube to each vertex of cubes of CCC2 having degree 3 or you can say by attaching cubes by an edge to all the white vertices of CCC2. So, at each level, a new set of cubes is attached by edges to the white vertices of cubes of the preceding level. The third level of CCCn is displayed in Figure 2 which is constructed and presented in a most suitable manner to explain the structure of CCCn.Figure 1
Crystal cubic carbon structureCCC2.Figure 2
Crystal cubic carbon structureCCC3, with CCC1 as the central cube.All the new attached cubes, at each level, will be called the outermost layer of cubes or outermost level of cubes, or you can say at each level, the cubes with white vertices will be called the outermost layer. As inCCC2, the outermost layer of cubes consists of 8 cubes. Because there are 7×8 vertices of degree 3, so in CCC3, the outermost layer of cubes will consist of 7×8 cubes. Similarly, this procedure is repeated to get the next level. The cardinality of vertices and edges in CCCn is given below, respectively.(1)VCCCn=224∑r=3n23−1r−3+3123−1n−2+2∑r=0n−223−1r+3,ECCCn=424∑r=3n23−1r−3+2423−1n−2+2∑r=0n−223−1r+3.There are some articles that describe the different topological properties ofCCCn structure, the famous of those topological indices are Randic, ABC, and Zagreb indices and other degree-based indices of CCCn which are computed in [15–18]. In the articles [19, 20], theauthors calculated eccentricity and Szeged-type topological indices of CCCn. The aim of this article is to compute the metric dimension of CCCn. Note that if W=w1,w2,…,wk is the ordered set of vertices of a graph G, then ξth component of rc|W is 0⟺c=wξ. Thus, in order to show that W is a resolving set, it suffices to verify that ra|W≠rb|W for each pair of distinct vertices a,b∈VG\W.


## 2. Main Result

In this section, we will present the main result about theβCCCn. But before going further, let us discuss the very simple case of CCC1 which is just a cube. We claim that βCCC1=3 indeed is true, let us see how.Assume thatβCCC1=1, and because of symmetry, we can take any vertex of cube to be the resolving set as in Figure 3(a), say W=a, then rb|W=rc|W, which is a contradiction. So, βCCC1>1. Assume that βCCC1=2. Then, there are two possibilities for the elements of the resolving set W of CCC1 because of its symmetric shape. The possible cases are as follows:(I)
The two elements ofW are the vertices on the main diagonal of CCC1.(II)
The two elements ofW are on the same face of the cube. In this case, the both elements are either on the main diagonal of a face or on the same edge of a face.Figure 3
The graph ofCCC1 with all options of possible resolving sets.
(a)(b)(c)(d)(e)Without loss of generality, we can assume thatW=a,f for case (I). For case (II) without loss of generality, we can assume W=a,c and W=b,c, respectively. Then, Figures 3(b)–3(d) show that βCCC1≠2; the ordered pairs in these Figures denote the representations of the vertices. Thus, from Figure 3(e), it is proved that βCCC1=3.Now, we will prove the main result of this article.Theorem 1.
The metric dimension of crystal cubic carbon structureCCCn is 7n−2×16, for all n≥2, that is, βCCCn=7n−2×16,∀n≥2.Proof.
LetG=CCCn be the crystal cubic carbon structure and n≥2. To show that the βCCCn=7n−2×16 firstly, we will show that βCCCn≥7n−2×16. Let Qn be a cube on the outermost layer of CCCn, as depicted in Figure 4 (note that there are no cubes attached to the vertices b1,b2,b3,c1,c2,c3,andu). In other words, all these vertices are of degree 3 and they belong to only one cube which is Qn. Observe that the red vertex of cube Qn is attached with red edge to a cube Qn−1 of the preceding level at its blue vertex. Also, note that db1,a=1=db2,a=db3,a and dc1,a=2=dc2,a=dc3,a and du,a=3.
LetW=w1,w2,…,wk be a resolving set of CCCn. We claim that at least two vertices of Qn belong to W. Suppose on contrary that no vertex of Qn belongs to W and let ra|W be a representation of vertex a∈VQn. Note that all the shortest paths from any vertex of Qn to any vertex of W contain the vertex a of Qn. So, we can say that all such paths pass through vertex a (path may end at it). Then,(2)rb1|W=db1,w1,db1,w2,…,db1,wk=da,w1+1,da,w2+1,…,da,wk+1=db2,w1,db2,w2,…,db2,wk=rb2|W;this is a contradiction. Now, assume that exactly one vertex from the set VQn belongs to W. Without loss of generality, we can assume that this common vertex is w1.Case 1. If w1=a, then(3)rb1|W=1,db1,w2,…,db1,wk=1,db2,w2,…,db2,wk=rb2|W, a contradiction.Case 2. If w1=b1, then dc1,w1=1=dc2,w1(4)rc1|W=1,dc1,w2,…,dc1,wk=1,dc2,w2,…,dc2,wk=rc2|W,again a contradiction.Similar contradictions appear forw1=b2 and w1=b3, let us look at it.Case 3. If w1=b2, then dc1,w1=1=dc3,w1(5)rc1|W=1,dc1,w2,…,dc1,wk=1,dc3,w2,…,dc3,wk=rc3|W,a contradiction.Case 4. If w1=b3, then dc2,w1=1=dc3,w1(6)rc2|W=1,dc2,w2,…,dc2,wk=1,dc3,w2,…,dc3,wk=rc3|W,a contradiction.Case 5. If w1=c1, then db1,w1=1=db2,w1(7)rb1|W=1,db1,w2,…,db1,wk=1,db2,w2,…,db2,wk=rb2|W,a contradiction.Case 6. If w1=c2, then db1,w1=1=db3,w1(8)rb1|W=1,db1,w2,…,db1,wk=1,db3,w2,…,db3,wk=rb3|W,a contradiction.Case 7. If w1=c3, then db2,w1=1=db3,w1(9)rb2|W=1,db2,w2,…,db2,wk=1,db3,w2,…,db3,wk=rb3|W,a contradiction.Case 8. If w1=u, then db1,w1=1=db3,w1(10)rb1|W=1,db1,w2,…,db1,wk=1,db3,w2,…,db3,wk=rb3|W,a contradiction.
The contradiction in all the cases proved our claim. So, at least two vertices from the vertex set ofQn are in the resolving set W of CCCn. Since Qn was taken arbitrary, so W contains at least two vertices from each of the cube in the outermost layer of cubes of CCCn. By the construction of CCCn, we can see that at each step or at each level, the cubes in CCCn are increased by a number equal to 7 multiplied by the number of cubes in the outermost layer of the previous level. For example, in CCC2, we have 8 cubes in the outer layer, and in CCC3, we have 7×8 cubes in the outermost layer. Thus, there are exactly 7n−2×8 cubes in the outermost layer of CCCn. Since from each such cube there are at least two vertices in W, so βCCCn≥7n−2×16.Figure 4
An arbitrary cubeQn in the outermost layer of cubes of CCCn.


### 2.1. Second Part of Proof

In this part, we will show thatβCCCn≤7n−2×16. Let W=w1,w2,…,wk be the collection of all the vertices of type b1 and b2 just like we have discussed in part one of the proof and depicted in Figure 4. Then, k=7n−2×16. We claim that W is a resolving set of CCCn. The representations of the two arbitrary vertices of CCCn can be compared in five different cases and they are discussed as follows:(1)
The two arbitrary selected vertices are on the same cube in the outermost level ofCCCn (see Figure 4).(2)
The two arbitrary selected vertices are on the same cube, but this cube is not the outer most cube and neither the central cube (i.e.,CCC1), as depicted in Figure 5.(3)
The two arbitrary selected vertices are on the central cube, as displayed in Figure6.(4)
The two arbitrary selected vertices are on a chain of cubes with one end being the cube of the outermost level (see Figure7).(5)
The two arbitrary selected vertices are on distinct chains of cubes and those chains are connecting at a cube which we can call a branching cube. As explained in Figure8, in which B cube is the branching cube, S-cube and T-cube are on different chains each containing one of the selected vertices.Case (1). This can be proved by a direct computation for the representation of all the vertices in this cube (Figure 4). Without loss of generality, we can assume that w1=b1,w2=b2∈W, then ra|W=1,1,da,w3,…,da,wk and(11)rb3|W=2,2,da,w3+1,…,da,wk+1,rc1|W=1,1,da,w3+2,…,da,wk+2,rc2|W=1,3,da,w3+2,…,da,wk+2,rc3|W=3,1,da,w3+2,…,da,wk+2,ru|W=2,2,da,w3+3,…,da,wk+3.We can see from the above that these representations are all distinct in this case.Case (2). Let the two arbitrary selected vertices be on the same cube and this cube is not on the outermost cube and neither is it the central cube. A visualization of such cube is given in Figure 5. We can label the vertices of this cube QA, as shown in Figure 5. Without loss of generality, we can assume that w1,w2 are on the cube in the outermost layer of cubes and that cube is connected to cube QA at vertex u1 by a chain of cubes. Similarly, we can assume that w2i−1,w2i are on the cube in the outermost layer of cubes and those cubes are connected to cube QA at vertices ui, i=2,…,7, by a chain of cubes, respectively.(12)du1,w1≠dui,w1,i=1,…,7andi≠1,du2,w3≠dui,w3,i=1,…,7andi≠2,du3,w5≠dui,w5i=1,…,7andi≠3,du4,w7≠dui,w7,i=1,…,7andi≠4,du5,w9≠dui,w9,i=1,…,7andi≠5,du6,w11≠dui,w11,i=1,…,7andi≠6,du7,w13≠dui,w13,i=1,…,7andi≠7.Also,(13)da,w1=du1,w1+1,da,w3=du2,w3+1,da,w5=du3,w5+1,da,w7=du4,w7+2,da,w9=du5,w9+2,da,w11=du6,w11+2,andda,w13=du7,w13+3. All these computations show that rui|W≠ruj|W for i≠j and ra|W≠rui|W for i=1,…,7. This completes the proof in this case.Case (3). Assume that the two arbitrary selected vertices are on the central cube, as displayed in Figure 6, where just like in the previous case (2), we have labeled all 8 vertices with u1,u2,…,u8. Again, without loss of generality, we assume that w2i−1,w2i,i=1,…,8, are on the cube in the outermost layer of cubes and those outermost cubes containing w2i−1,w2i are connected to the central cube CCC1 at vertices ui, i=1,2,…,8, by a chain of cubes, respectively. These assumptions imply that(14)du1,w1≠dui,w1,1≤i≤8andi≠1,du2,w3≠dui,w3,1≤i≤8andi≠2,du3,w5≠dui,w5,1≤i≤8andi≠3,du4,w7≠dui,w7,1≤i≤8andi≠4,du5,w9≠dui,w9,1≤i≤8andi≠5,du6,w11≠dui,w11,1≤i≤8andi≠6,du7,w13≠dui,w13,1≤i≤8andi≠7,du8,w15≠dui,w15,1≤i≤8andi≠8.So, we get the conclusion that, in this case, againrui|W≠rui|W for i≠j and 1≤i≤8, 1≤j≤8.Case (4). Now, we are going to discuss case (4). Assume that the two arbitrary selected vertices s,t are on two distinct cubes and those cubes are on a chain of cubes, see Figure 7. Assume that one end of this chain is the outermost cube containing two arbitrary resolving elements, say w1,w2 (without loss of generality, we can assume that those vertices are w1,w2), and the other end is the central cube.As depicted in Figure7, let t be a vertex of cube Qt and s be a vertex of cube Qs, then ds,w1<dt,w1, and therefore, rs|W≠rt|W. This completes the proof in this case.Case (5). Finally, suppose that the two arbitrary selected vertices s,t are on distinct chains of cubes and those chains are connecting at a cube which we can call a branching cube; this branching cube can also be the central cube. As explained in Figure 8, in which B cube is the branching cube, S cube and T cube are on different chains each containing one of the selected vertices, that is, s∈VS and t∈VT. Both of the two cubes S and T or any one of these cube can also be the cubes in the outermost level of cubes.Figure 5
Arbitrary cubeQA not in the outermost layer of cubes of CCCn and nor the central cube. This cube is connected to the central cube by a chain of cubes at vertex a.Figure 6
Central cube ofCCCn, that is, the cube CCC1.Figure 7
A chain of cubes with one end being the cube of the outermost level;Qs and Qt are arbitrary cubes on the chain but not the outermost cubes.Figure 8
Branching cube and chain of cubes inCCCn.Note: in the idea of case (4), we can say that someone can select two vertices on different cubes such that there is chain of cube connecting them and both ends of this chain are the cubes on the outermost level of cubes. But then, there must be a cube (which we call branching cube) in this chain that connects to the central cube by the chain of cubes.) Without loss of generality, we can assume thatwi=w1,wi+1=w2 and wj=w3,wj+1=w4. We can see that the length of the shortest path from vertex w1 to vertex t of cube T is greater than the length of the shortest path from vertex w1 to vertex s of cube S. Thus, ds,w1≠dt,w1, so this implies that rs|W≠rt|W.All these five cases prove thatW=w1,w2,…,wk is a resolving set. Since there are 7n−2×16 number of elements in W, therefore the proof of theorem concludes.


## 2.1. Second Part of Proof

In this part, we will show thatβCCCn≤7n−2×16. Let W=w1,w2,…,wk be the collection of all the vertices of type b1 and b2 just like we have discussed in part one of the proof and depicted in Figure 4. Then, k=7n−2×16. We claim that W is a resolving set of CCCn. The representations of the two arbitrary vertices of CCCn can be compared in five different cases and they are discussed as follows:(1)
The two arbitrary selected vertices are on the same cube in the outermost level ofCCCn (see Figure 4).(2)
The two arbitrary selected vertices are on the same cube, but this cube is not the outer most cube and neither the central cube (i.e.,CCC1), as depicted in Figure 5.(3)
The two arbitrary selected vertices are on the central cube, as displayed in Figure6.(4)
The two arbitrary selected vertices are on a chain of cubes with one end being the cube of the outermost level (see Figure7).(5)
The two arbitrary selected vertices are on distinct chains of cubes and those chains are connecting at a cube which we can call a branching cube. As explained in Figure8, in which B cube is the branching cube, S-cube and T-cube are on different chains each containing one of the selected vertices.Case (1). This can be proved by a direct computation for the representation of all the vertices in this cube (Figure 4). Without loss of generality, we can assume that w1=b1,w2=b2∈W, then ra|W=1,1,da,w3,…,da,wk and(11)rb3|W=2,2,da,w3+1,…,da,wk+1,rc1|W=1,1,da,w3+2,…,da,wk+2,rc2|W=1,3,da,w3+2,…,da,wk+2,rc3|W=3,1,da,w3+2,…,da,wk+2,ru|W=2,2,da,w3+3,…,da,wk+3.We can see from the above that these representations are all distinct in this case.Case (2). Let the two arbitrary selected vertices be on the same cube and this cube is not on the outermost cube and neither is it the central cube. A visualization of such cube is given in Figure 5. We can label the vertices of this cube QA, as shown in Figure 5. Without loss of generality, we can assume that w1,w2 are on the cube in the outermost layer of cubes and that cube is connected to cube QA at vertex u1 by a chain of cubes. Similarly, we can assume that w2i−1,w2i are on the cube in the outermost layer of cubes and those cubes are connected to cube QA at vertices ui, i=2,…,7, by a chain of cubes, respectively.(12)du1,w1≠dui,w1,i=1,…,7andi≠1,du2,w3≠dui,w3,i=1,…,7andi≠2,du3,w5≠dui,w5i=1,…,7andi≠3,du4,w7≠dui,w7,i=1,…,7andi≠4,du5,w9≠dui,w9,i=1,…,7andi≠5,du6,w11≠dui,w11,i=1,…,7andi≠6,du7,w13≠dui,w13,i=1,…,7andi≠7.Also,(13)da,w1=du1,w1+1,da,w3=du2,w3+1,da,w5=du3,w5+1,da,w7=du4,w7+2,da,w9=du5,w9+2,da,w11=du6,w11+2,andda,w13=du7,w13+3. All these computations show that rui|W≠ruj|W for i≠j and ra|W≠rui|W for i=1,…,7. This completes the proof in this case.Case (3). Assume that the two arbitrary selected vertices are on the central cube, as displayed in Figure 6, where just like in the previous case (2), we have labeled all 8 vertices with u1,u2,…,u8. Again, without loss of generality, we assume that w2i−1,w2i,i=1,…,8, are on the cube in the outermost layer of cubes and those outermost cubes containing w2i−1,w2i are connected to the central cube CCC1 at vertices ui, i=1,2,…,8, by a chain of cubes, respectively. These assumptions imply that(14)du1,w1≠dui,w1,1≤i≤8andi≠1,du2,w3≠dui,w3,1≤i≤8andi≠2,du3,w5≠dui,w5,1≤i≤8andi≠3,du4,w7≠dui,w7,1≤i≤8andi≠4,du5,w9≠dui,w9,1≤i≤8andi≠5,du6,w11≠dui,w11,1≤i≤8andi≠6,du7,w13≠dui,w13,1≤i≤8andi≠7,du8,w15≠dui,w15,1≤i≤8andi≠8.So, we get the conclusion that, in this case, againrui|W≠rui|W for i≠j and 1≤i≤8, 1≤j≤8.Case (4). Now, we are going to discuss case (4). Assume that the two arbitrary selected vertices s,t are on two distinct cubes and those cubes are on a chain of cubes, see Figure 7. Assume that one end of this chain is the outermost cube containing two arbitrary resolving elements, say w1,w2 (without loss of generality, we can assume that those vertices are w1,w2), and the other end is the central cube.As depicted in Figure7, let t be a vertex of cube Qt and s be a vertex of cube Qs, then ds,w1<dt,w1, and therefore, rs|W≠rt|W. This completes the proof in this case.Case (5). Finally, suppose that the two arbitrary selected vertices s,t are on distinct chains of cubes and those chains are connecting at a cube which we can call a branching cube; this branching cube can also be the central cube. As explained in Figure 8, in which B cube is the branching cube, S cube and T cube are on different chains each containing one of the selected vertices, that is, s∈VS and t∈VT. Both of the two cubes S and T or any one of these cube can also be the cubes in the outermost level of cubes.Figure 5
Arbitrary cubeQA not in the outermost layer of cubes of CCCn and nor the central cube. This cube is connected to the central cube by a chain of cubes at vertex a.Figure 6
Central cube ofCCCn, that is, the cube CCC1.Figure 7
A chain of cubes with one end being the cube of the outermost level;Qs and Qt are arbitrary cubes on the chain but not the outermost cubes.Figure 8
Branching cube and chain of cubes inCCCn.Note: in the idea of case (4), we can say that someone can select two vertices on different cubes such that there is chain of cube connecting them and both ends of this chain are the cubes on the outermost level of cubes. But then, there must be a cube (which we call branching cube) in this chain that connects to the central cube by the chain of cubes.) Without loss of generality, we can assume thatwi=w1,wi+1=w2 and wj=w3,wj+1=w4. We can see that the length of the shortest path from vertex w1 to vertex t of cube T is greater than the length of the shortest path from vertex w1 to vertex s of cube S. Thus, ds,w1≠dt,w1, so this implies that rs|W≠rt|W.All these five cases prove thatW=w1,w2,…,wk is a resolving set. Since there are 7n−2×16 number of elements in W, therefore the proof of theorem concludes.


## 3. Conclusion

In this article, we have studied the metric dimension of the crystal cubic carbon structure and we gave a formula for its metric dimension. We have found that the metric dimension ofCCCn is not constant and find its closed form.



---

*Source: 3438611-2021-07-02.xml*