Received 16 February 2016; accepted 22 April 2016; published 25 April 2016

ABSTRACT

An ordered set W of vertices of a graph G is called a resolving set, if all the vertices of G are uniquely determined by the vector of distances to the vertices in W. The metric dimension of G is the minimum cardinality of a resolving set of G. A resolving set W for G is fault-tolerant if W\{v} is also a resolving set, for each v in W, and the fault-tolerant metric dimension of G is the minimum cardinality of such a set. In this paper we determine the metric dimension and fault-tolerant metric dimension problems for the graphs of certain crystal structures.

Keywords:

Resolving Set, Metric Dimension, Fault-Tolerant metric Dimension, Crystal Structures, Bismuth Tri-Iodide, Lead Chloride, Quartz

1. Introduction

Let G be a connected graph with vertex set V and edge set E. The distance d(u, v) between two vertices u, v Î V is the length of a shortest path between them. Let be an ordered set of vertices of G and let v be a vertex of G. The representation r(v|W) of v with respect to W is the k-tuple. Then W is a resolving set for G if and only if no two vertices of G have the same representation with respect to W. A resolving set of minimum cardinality is called a basis for G and this cardinality is the metric dimension of G, denoted by β(G). Note that w_i is the only vertex of W for which the ith co-ordinate of its representation with respect to W is 0. Therefore, when checking if W is a resolving set for G, it suffices to consider pair of vertices x, y Î V\W. A resolving set W for G is fault-tolerant if W\{v} is also a resolving set, for each v in W. A fault-tolerant resolving set of minimum cardinality is called a fault-tolerant metric basis for G and this cardinality is the fault-tolerant metric dimension of G, denoted by β′(G).

Slater [1] introduced the concept of a resolving set for a connected graph which was also independently discovered by Harary and Melter [2] . Melter et al. [3] studied the metric dimension problem for grid graphs induced by lattice points in the plane when the distances are measured in the L₁ and L_¥ metrics. Khuller et al. [4] have proved that the metric dimension of a d-dimensional grid is d, generalizing the result of Melter et al. [3] . They have obtained a linear time algorithm to find the metric dimension of trees. They have considered graphs that require only a few landmarks and have shown that paths are the only graphs with β = 1. Further they have shown that a graph G with β(G) = 2 can have neither K₅ nor K_3;3 as a subgraph. By extending this they have stated that a graph G with β(G) = k cannot have as a subgraph. Using these facts they have conjectured that graphs having β(G) = 2 might be planar, but have exhibited a non-planar graph with β(G) = 2. It is also shown that the metric dimension of a graph with n nodes can be approximated in polynomial time within a factor of O(logn).

Hernando et al. [5] make a general study of the metric dimension of Cartesian products of graphs. Part of their motivation for studying the metric dimension of Cartesian products is that in two of the applications, namely Mastermind and coin weighing, the graphs that arise are Cartesian products. It was noted in [6] that determining the metric dimension of a graph is an NP-hard problem. Manuel et al. [7] have shown that the problem remains NP-complete for bipartite graphs. This problem has been studied for trees, multi-dimensional grids [4] , Petersen graphs [8] , torus networks [9] , Benes networks [7] , honeycomb networks [10] , enhanced hypercubes [11] , circulant networks [12] , circulant and Harary graphs [13] .

The metric dimension concepts have some applications in chemistry for representing chemical components, the navigation of robots in networks [4] , image processing and pattern recognition. Interconnection networks are designed for use at different levels within and across computer systems to meet the operational demands of various application areas. In Chapter 18 of Parallel and Distributed Computing Handbook, by Albert Y. Zomaya, Stojmenović [14] suggests a number of open problems for various interconnection networks. One of them is about designing new architectures. He writes: “Designing new architectures remains an area of intensive investigation given that there is no clear winner among existing ones”. Motivated by this statement we aim at defining and constructing new architectures and we begin our search in the field of chemical structures.

In this paper we consider graphs of certain crystal structures and determine the metric dimension and fault tolerant metric dimension.

2. Crystal Structures

The physical structure of solid materials of engineering importance depends mainly on the arrangements of the atoms, ions, or molecules that make up the solid and the bonding forces between them. If the atoms or ions of a solid are arranged in a pattern that repeats itself in three dimensions, they form a solid that is said to have a crystal structure and is referred to as a crystalline solid or crystalline material. The atomic arrangement or crystalline structure of a material is important in determining the behavior and properties of a solid material. Examples of crystalline materials are metals, alloys, and some ceramic materials. The unit cell is the smallest structural unit or building block that can describe the crystal structure. Repetition of the unit cell generates the entire crystal. In this paper, we investigate the metric dimension and fault-tolerant metric dimension problems for the graphs bismuth tri-iodide, lead chloride and quartz (crystalline SiO₂).

2.1. The Graph of Bismuth Tri-Iodide

Bismuth tri-iodide (BiI3) is an inorganic compound. It is the product of the reaction of bismuth and iodine, which once was of interest in qualitative inorganic analysis. Layered BiI3 crystal is considered to be a three-layered stacking structure, where bismuth atom planes are sandwiched between iodide atom planes, which form the sequence I-Bi-I planes. The periodic stacking of three layers forms rhombohedral BiI3 crystal with R-3 symmetry [15] [16] . The successive stacking of one I-Bi-I layer forms hexagonal structure with symmetry [17] [18] . A single crystal of BiI3 has been synthesized by Nason and Keller [19] . Figure 1 shows one unit of bismuth tri-iodide.

The graph of a single unit of bismuth tri-iodide contains six 4-cycles of which two are on the top, two are in

the middle and two at the bottom. The unit cells of bismuth tri-iodide can be arranged either linearly or in a sheet form. A linear arrangement with m unit cells is called an m-bismuth chain; mn unit cells arranged into m rows and n columns is called an m × n bismuth sheet.

We first obtain a lower bound for the metric dimension of an m-bismuth chain.

Lemma 1. Let G be an m-bismuth chain. Then b(G) ≥ 7m + 5.

Proof. The two 2-degree vertices of each 4-cycle are equidistant from every vertex of G. So one of them must belong to any resolving set. Similarly the two 1-degree vertices incident with a common vertex are equidistant from every vertex of G. So one of them must belong to any resolving set. Hence b(G) ≥ 7m + 5.

Our next result realizes the lower bound obtained in Lemma 1.

Theorem 1. Let G be an m-bismuth chain. Then b(G) ≤ 7m + 5.

Proof. The cycles in an m-bismuth chain are listed as, and, and. Let p_i, q_i, , , and, and be the vertices as indicated in Figure 2. We claim that is a resolving set. Let u, v Î V\W.

Case 1:, for some j,.

If u and v are adjacent, then resolves them. If u and v are non-adjacent in, then they are equidistant from x_j. In this case either x_j?1 or x_j+1 resolves u and v. This argument holds for. If j = 1 or 2m, then or resolves u and v respectively. The argument is similar if or, and.

Case 2: and.

In this case u and v are resolved by q_s,. The argument is similar if and or and. In both cases a leaf vertex resolves u and v.

Lemma 1 and Theorem 1 solve the metric dimension problem for an m-bismuth chain completely. Thus we have the following result.

Theorem 2. Let G be an m-bismuth chain. Then b(G) = 7m + 5.

Fault-Tolerant Metric Dimension

In the proof of Theorem 2, we constructed a metric basis W consisting of a 2-degree vertex from each 4-cycle and a leaf vertex from each of the pair of leaf incident with a 4-cycle.

Let W^* be the set of all 2-degree vertices and all the leaves vertices. Clearly W^* is a resolving set being a superset of the constructed resolving set W.

It is easy to see that representations of any two vertices u, v Î V\W^* will differ in at least two distinct places. Hence W^* is a fault-tolerant metric basis.

Theorem 3. Let G be an m-bismuth chain. Then.

We state the results for m × n-bismuth sheet.

Theorem 4. Let G be an m × n-bismuth sheet. Then.

Theorem 5. Let G be an m × n-bismuth sheet. Then.

2.2. The Graph of Lead Chloride

Lead chloride is a halide crystal which occurs naturally in the form of mineral cotunnite. It is used in the production of infra red transmitting glass and basic chloride of lead known as patteson’s white lead, perry, ornamental glass called aurene glass, stained glass. It is also used as an intermediate in refining bismuth (Bi) ore, it is used in the synthesis of organometallic, lead titanate and barium titanate. The structure of lead chloride is orthorhombic dipyramidal.

The graph of a single unit of lead chloride is obtained from that of bismuth tri-iodide by joining just one 2-degree vertex of each of the 4-cycles to a new vertex.

As in the case of bismuth tri-iodide, chains and sheets of lead chloride are defined.

Lemma 2. Let G be an m-lead chloride chain. Then.

Proof. Every pair of 1-degree vertices incident with a common vertex are equidistant from every vertex of the graph. Hence at least one vertex must belong to any resolving set. Hence.

We adopt a labeling scheme in which vertices are listed level wise (levels 1 to 7) from top to bottom. The notation will depict the ith vertex in level k.

Theorem 6. Let G be an m-lead chloride chain. Then.

Proof. Let p_i, q_i, , be the 1-degree vertices as shown in Figure 3. We claim that is a resolving set. Let u, v Î V\W.

Case 1: u, v belong to the same level.

In view of the symmetry of the graph, it is enough to consider vertices in levels 1 to 4. Any two vertices on level 1 are resolved by either or. Now we consider any two vertices on level 2. Without loss of generality let us assume that, and,. In this case either or resolves u and v. In fact if i = 3s ? 1, 1 ≤ s ≤ m, then and. Similar argument will hold if i = 3s or i = 3s +1. The argument is similar for any two vertices in the level 3 except for the pairs of vertices and. These pairs are equidistant, respectively, from and. The pair is resolved by and the pair is resolved by. The similar argument holds for the level 4.

Case 2: u, v belong to different levels.

Different level vertices are resolved by any p_i or q_j,.

Lemma 2 and Theorem 6 solve the metric dimension problem for an m-lead chloride chain completely. Thus we have the following result.

Theorem 7. Let G be an m-lead chloride chain. Then.

Theorem 8. Let G be an m-lead chloride chain. Then.

2.3. The Graph of Quartz (Crystalline SiO₂)

Quartz is a crystalline form of silicon dioxide with formula SiO₂. A quartz network can be built in various ways. The quartz network of dimension 1 is a 12-cycle. The quartz network of dimension n consists n² number of 12-cycles and these 12-cycles are arranged in the shape of a rhombus. Figure 4 depicts a quartz network of

dimension 3.

Theorem 2.11. Let G be the graph of quartz. Then b(G) = 2.

Proof. It is easy to see that {a, b} is a resolving set. This follows by using the underlying binarytree structure rooted at a. Vertices at different levels are resolved by the root and vertices at the same level are resolved by b.

Theorem 2.12. Let G be the graph of quartz. Then b′(G) = 4.

3. Conclusion

In this paper we have solved the metric dimension and fault-tolerant metric dimension problems for the graphs of certain crystal structures. This problem is under investigation for certain nanostructures.

Cite this paper

Sathish Krishnan,Bharati Rajan,1 1,1 1, (2016) Fault-Tolerant Resolvability of Certain Crystal Structures. Applied Mathematics,07,599-604. doi: 10.4236/am.2016.77055

References