Shehnaz Akhter, Rashid Farooq

School of Natural Sciences, National University of Sciences and Technology, H-12 Islamabad, Pakistan.

shehnazakhter36@yahoo.com, farook.ra@gmail.com

A resolving set W is a set of vertices of a graph G(V, E) such that for every pair of distinct vertices u, v ∈ V (G), there exists a vertex w ∈ W satisfying d(u, w) 6= d(v, w). A resolving set with minimum number of vertices is called metric basis of G. The metric dimension of G, denoted by dim(G), is the minimum cardinality of a resolving set of G. In this paper, we consider (3, 6) fullerene and (4, 6)-fullerene graphs and compute the metric dimension for these fullerene graphs. We also give conjecture on the metric dimension of (3, 6)-fullerene and (4, 6)-fullerene graphs.

Keywords: resolving set, metric dimension, fullerene graph

Mathematics Subject Classification : 05C12

DOI: 10.5614/ejgta.2019.7.1.7

1. Introduction

The metric dimension was initially studied by Slater [16] and Harary and Melter [7]. They characterized the metric dimension of trees. Metric dimension has several applications in robot navigation [9], chemistry [3], sonar [16] and combinatorical optimization [13]. Let G be a molecular graph, that is, a representation of the structural formula of a chemical compound in terms of graph theory. The vertices and edges of G correspond to atoms and chemical bonds, respectively. For u, v ∈ V (G), the length of a shortest path from u to v is called the distance between u and v and is denoted by d(u, v). A graph G is said to be k-connected if there does not exist a set of less than k vertices whose removal disconnects the graph G. A planar graph G is a graph that can be drawn in such a way that no two edges cross each other. A cubic graph G is a graph in which all vertices have degree 3.

Received: 25 July 2017, Revised: 13 September 2018, Accepted: 28 December 2018.

A vertex w of G resolves a pair u, v of vertices if d(w, u) 6= d(w, v). Let W = {w1, w2, . . . , wk} ⊂ V (G). The metric representation of a vertex v ∈ V (G) with respect to W is the k-tuple

\[r(v|W) = (d(v, w_1), d(v, w_2), \dots, d(v, w_k)).\]

If every pair of distinct vertices of G have a distinct metric representation then the ordered set W is called a resolving set of G. A resolving set of minimum cardinality is called the metric basis for G and this cardinality is the metric dimension of G, denoted by dim(G). If dim(G) = k, then G is said to be k-dimensional. Several variations of metric dimension have been discussed in the literature, like resolving dominating sets [2], independent resolving sets [4], local metric sets [11], resolving partitions [5] and strong metric generators [13].

In 1985, Kroto et al. [8] discovered fullerene molecule and since then, scientists took a great interest in the fullerene graphs. A (k, 6)−fullerene graph is a 3-connected cubic plane graph whose faces have sizes k and 6. The only values of k for which a (k, 6)−fullerene graph exists are 3, 4 and 5. A (5, 6)−fullerene is an ordinary fullerene and constructed from pentagons and hexagons. Fowler et al. [6] discussed the mathematical properties of (5, 6)−fullerene.

A (3, 6)-fullerene graph have attained attention due to the similarity of its structure with ordinary fullerenes. The Eulers formula implies that a (3, 6)-fullerene graph has exactly four faces of size 3 and (n/2) − 2 hexagons. If the triangles in (3, 6)-fullerene have no common edge then it is called isolated triangular rules (ITR).

A (4, 6)-fullerene graph is a mathematical model of a boron-nitrogen fullerene. The Eulers formula implies that a (4, 6)-fullerene graph has exactly six square faces and (n/2) − 4 hexagons. If the six quadrangles in (4, 6)-fullerene don't have common edge, then it is called isolated square rules (ISR).

Ashrafi et al. [1] calculated the topological indices of (3, 6)- and (4, 6)-fullerene graphs. Koorepazan-Moftakhar et al. [10] find the automorphism group and fixing number of (3, 6)- and (4, 6)-fullerene graphs.

Siddiqui et al. [14, 15] calculated the metric dimension and partition dimension of Nanotubes. Rajan, et al. [12] calculated the metric dimension of enhanced hypercube networks. In this paper, we consider (3, 6)-fullerene and (4, 6)-fullerene graphs and compute their metric dimension. We also give conjecture on the metric dimension of (3, 6)-fullerene and (4, 6)-fullerene graphs.

2. Metric dimension of (3,6)-fullerene graphs

Let F1[n], F2[n], F3[n] and F4[n] are the graphs of (3, 6)-fullerene depicted in Figures ??-4 with order 8n + 4, 12n + 4, 16n − 32 and 24n, respectively. In this section, we find the metric dimension of F1[n], F2[n], F3[n] and F4[n] fullerene graphs.

Theorem 2.1. The metric dimension of fullerene graph F1[n] is 3.

Proof. Let {z1, z2, z3} and {z4, z5, z6} be the vertex sets of outer triangles of F1[n]. Let W = {z2, z3, z5} ⊂ V (F1[n]). We show that W is a resolving set of F1[n]. For this we give the representation of vertices in V (F1[n]) \ W with respect to W. The representation of vertices z1, z⁴ and z⁶ is given by:

\[r(z_1|W) = (1,1,2), \quad r(z_4|W) = (2,2,1), \quad r(z_6|W) = (3,3,1).\]

Figure 1. The Graph \(F_1[n]\).

The representation of vertices of upper half of the fullerene graph \(F_1[n]\) is given by:

\[r(x_i|W) = \begin{cases} (i, i+1, i+1), & \text{if } 1 \le i \le 2n-1, \\ (2n, 2n+1, 2n), & \text{if } i = 2n, \\ (4n-i+1, 4n-i+2, 4n-i), & \text{if } 2n+1 \le i \le 4n-1. \end{cases}\]

The representation of vertices of lower half of the fullerene graph \(F_1[n]\) is given by:

\[r(y_i|W) = \begin{cases} (i+1, i, i+2), & \text{if } 1 \le i \le 2n-1, \\ (2n-1, 2n-2, 2n-1), & \text{if } i = 2n, \\ (4n-i+2, 4n-i+1, 4n-i+1), & \text{if } 2n+1 \le i \le 4n-1. \end{cases}\]

All the vertices of \(F_1[n]\) have different representation with respect to W, this implies that W is a resolving set of \(F_1[n]\). Thus the metric dimension of \(\dim(F_1[n]) \leq 3\).

On the other hand, we show that \(\dim(F_1[n]) \geq 3\) by proving that there is no resolving set W' such that |W'| = 2. Let \(A = \{z_1, z_2, z_3, z_4, z_5, z_6\}\) be the set of vertices of outer triangles of \(F_1[n]\). Suppose on contrary that \(\dim(F_1[n]) = 2\) and W' is a resolving set with |W'| = 2, then there are following cases:

Case 1. If both vertices of W' are in upper half of the fullerene graph \(F_1[n]\), then the representations of pair of vertices \(z_4\), \(z_6\) and \(z_1\), \(z_3\) are the same. Thus W' is not a resolving set of \(F_1[n]\).

Case 2. If both vertices of W' are in lower half of the fullerene graph \(F_1[n]\), then the representations of pair of vertices \(z_4\), \(z_5\) and \(z_1\), \(z_2\) are the same. Thus W' is not a resolving set of \(F_1[n]\).

Case 3. If one vertex of W' is from \(\{x_1, x_2, \dots, x_{4n-1}\}\) and other vertex is from \(\{y_1, y_2, \dots, y_{4n-1}\}\), then the pair of vertices \(z_1, z_5\) or \(z_2, z_6\) have the same representation with respect to W'. Thus W' is not a resolving set of \(F_1[n]\).

Case 4. If one vertex from upper half of fullerene graph \(F_1[n]\) and one from the set of vertices A in W', then the representation of some vertices in \(\{x_1, x_2, \cdots, x_{4n-1}\}\) and \(\{y_1, y_2, \cdots, y_{4n-1}\}\) is the same. Therefore W' is not a resolving set in this case.

Case 5. If one vertex from lower half of fullerene graph \(F_1[n]\) and one from the set of vertices A in W', then the representation of some vertices in \(\{x_1, x_2, \cdots, x_{4n-1}\}\) and \(\{y_1, y_2, \cdots, y_{4n-1}\}\) is the same. Therefore W' is not a resolving set in this case.

Case 6. If both vertices of W' belongs to the set of vertices A, then we have the following subcases:

• If \(W' = \{z_2, z_5\}\) or \(W' = \{z_2, z_6\}\), then the representation of pair of vertices \(x_1, z_1\) or \(x_1, z_3\) are the same. Similarly if \(W' = \{z_3, z_5\}\) or \(W' = \{z_3, z_6\}\), then the representation of pair of vertices \(y_1, z_1\) or \(y_1, z_2\) are the same.
• \(\bullet\) All other possible subsets of A, then the representation of remanning pair of vertices of set A is the same.

Thus, in every subcase we get a contradiction.

From above cases, we conclude that there is no resolving set W' containing two vertices of \(F_1[n]\). Thus the metric dimension of \(F_1[n]\) is 3. This completes the proof.

Figure 2. The Graph \(F_2[n]\).

Theorem 2.2. The metric dimension of fullerene graph \(F_2[n]\) is 3.

Proof. Let \(\{a_1, a_2, a_{12}\}\) and \(\{a_6, a_7, a_{11}\}\) be the vertex sets of outer triangles of \(F_2[n]\). Let \(W = \{a_1, a_2, a_{11}\} \subset V(F_2[n])\). We show that W is a resolving set of \(F_2[n]\). For this purpose, we give the representation of vertices in \(V(F_2[n]) \setminus W\) with respect to W. The representation of outer vertices of the fullerene graph \(F_2[n]\) is given below:

\[r(a_3|W) = (2,1,3), \quad r(a_4|W) = (3,2,3), \quad r(a_5|W) = (4,3,2),\]
\(r(a_6|W) = (5,4,1), \quad r(a_7|W) = (4,3,1), \quad r(a_8|W) = (3,2,2),\)
\(r(a_9|W) = (2,3,3), \quad r(a_{10}|W) = (1,2,4), \quad r(a_{12}|W) = (1,1,5).\)

The representation of vertices of upper half of the fullerene graph \(F_2[n]\) is given below:

\[r(x_i|W) = \begin{cases} (i+2, i+3, i+1), & \text{if } 1 \le i \le 2n-2, \\ (2n, 2n+1, 2n), & \text{if } i = 2n-1, \\ (4n-i-1, 4n-i, 4n-i), & \text{if } 2n \le i \le 4n-2, \\ (2, 3, 5), & \text{if } i = 4n-3. \end{cases}\]

The representation of middle vertices of the fullerene graph \(F_2[n]\) for n=1 is given below:

\[r(y_i|W) = \begin{cases} (4n-i, 4n-i, i), & \text{if } i = 2n-11, \\ (4n-i, 4n-i, 4n-i), & \text{if } i = 4n-2. \end{cases}\]

The representation of middle vertices of the fullerene graph \(F_2[n]\) for \(n \ge 2\) is given below:

\[r(y_i|W) = \begin{cases} (4,5,1), & \text{if } i = 1, \\ (i+3,i+3,i), & \text{if } 2 \le i \le 2n-2, \\ (4n-i,4n-i,i), & \text{if } 2n-1 \le i \le 2n, \\ (4n-i,4n-i,4n-i+1), & \text{if } 2n+1 \le i \le 4n-5, \\ (4n-i,4n-i,4n-i+3), & \text{if } 4n-4 \le i \le 4n-2. \end{cases}\]

The representation of vertices of lower half of the fullerene graph \(F_2[n]\) is given below:

\[r(z_i|W) = \begin{cases} (5,4,3), & \text{if } i = 1, \\ (i+3,i+3,i+2), & \text{if } 2 \le i \le 2n-2, \\ (2n+1,2n+1,2n+1), & \text{if } i = 2n-1, \\ (4n-i,4n-i,4n-i+1), & \text{if } 2n \le i \le 4n-3. \end{cases}\]

However all pair of vertices can easily be resolved by the set W. Thus the set W is a resolving set of \(F_2[n]\) and \(\dim(F_2[n]) \leq 3\). Now, we show that \(\dim(F_2[n]) \geq 3\) by showing that there is no resolving set W' such that |W'| = 2. Let \(A = \{a_1, a_2, a_3, \cdots, a_{12}\}\), \(B = \{x_1, x_2, \cdots, x_{4n-3}\}\), \(C = \{y_1, y_2, \cdots, y_{4n-3}\}\) and \(D = \{z_1, z_2, \cdots, z_{4n-3}\}\) be the sets of vertices of \(F_2[n]\). Suppose on contrary that \(\dim(F_2[n]) = 2\) and W' is a resolving set with |W'|. Then there are following possibilities:

Case 1. The pair of vertices \(a_1\), \(a_2\) and \(a_7\), \(a_8\) have the same distance from the vertices of set B, C and D. Then any subset of B, C and D is not a resolving set of \(F_2[n]\).

Case 2. If both vertices of W' are from set of vertices A, then some vertices of A have same representation. Therefore W' is not a resolving set of \(F_2[n]\).

Thus in every case we get a contradiction. Thus we conclude that there is no resolving set W' containing two vertices of \(F_2[n]\). Thus the metric dimension of \(F_2[n]\) is 3. This completes the proof.

Figure 3. The Graph \(F_3[n]\).

Theorem 2.3. The metric dimension of fullerene graph \(F_3[n]\) is 3.

Proof. Let {z1, z2, z3} and {z4, z5, z6} be the vertex sets of outer triangles and {a1, a2, a3, a4, a5, a6} be the vertices of outer hexagonal of F3[n]. Let W = {a5, z2, z5} ⊂ V (F3[n]). We need to show that W is a resolving set of F3[n]. For this purpose, first we give the representation of vertices in V (F3[n]) \ W with respect to W. The representation of outer vertices of fullerene graph F3[n] is given by:

\[r(a_1|W) = (2,3,4), \quad r(a_2|W) = (3,4,3), \quad r(a_3|W) = (2,5,2),\]
\(r(a_4|W) = (1,4,3), \quad r(a_6|W) = (1,2,5).\)

The representation of vertices of outer triangles in F3[n] is given by:

\[r(z_1|W) = (2, 1, 6), \quad r(z_3|W) = (3, 1, 7),\]
\(r(z_4|W) = (3, 6, 1), \quad r(z_6|W) = (4, 7, 1).\)

The representation of vertices of upper half of the fullerene graph F3[n] is given by:

\[r(x_i|W) = \begin{cases} (3,2,5), & \text{if } i = 1, \\ (i+2,i+1,i+2), & \text{if } 2 \le i \le 2n, \\ (2n+3,2n+2,2n+2), & \text{if } i = 2n+1, \\ (4n-i+5,4n-i+4,4n-i+3), & \text{if } 2n+2 \le i \le 4n, \\ (4,5,2), & \text{if } i = 4n+1. \end{cases}\]

The representation of middle vertices of the fullerene graph F3[n] for n = 1 is given by:

\[r(b_1|W) = (4, 1, 5), \quad r(b_2|W) = (4, 2, 4), \quad r(b_3|W) = (5, 3, 3),\]
\(r(b_4|W) = (5, 4, 2), \quad r(b_5|W) = (5, 5, 1).\)

The representation of middle vertices of the fullerene graph F3[n] for n ≥ 2 is given by:

\[r(b_i|W) = \begin{cases} (4, i, i+5), & \text{if } i \in \{1, 2\}, \\ (i+2, i, i+3), & \text{if } 3 \leq i \leq 2n-1, \\ (i+2, i, 4n-i+2), & \text{if } i \in \{2n, 2n+1\}, \\ (2n+3, 2n+2, 2n), & \text{if } i = 2n+2, \\ (4n-i+5, 4n-i+5, 4n-i+2), & \text{if } 2n+3 \leq i \leq 4n-1, \\ (5, 4n-i+7, 4n-i+2), & \text{if } i \in \{4n, 4n+1\}. \end{cases}\]

The representation of middle vertices of the fullerene graph F3[n] is given by:

\[r(c_i|W) = \begin{cases} (i+1,i+1,i+5), & \text{if } i \in \{1,2\}, \\ (i+1,i+1,i+4), & \text{if } 3 \le i \le 2n-1, \\ (i+1,i+1,4n-i+3), & \text{if } i \in \{2n,2n+1\}, \\ (2n+2,2n+3,2n+1), & \text{if } i = 2n+2, \\ (4n-i+4,4n-i+6,4n-i+3), & \text{if } 2n+3 \le i \le 4n-1, \\ (4n-i+4,4n-i+7,4n-i+3), & \text{if } i \in \{4n,4n+1\}. \end{cases}\]

The representation of vertices of lower half of the fullerene graph \(F_3[n]\) is given by:

\[r(y_i|W) = \begin{cases} (1,3,5), & \text{if } i = 1, \\ (i,i+2,i+3), & \text{if } 2 \le i \le 2n, \\ (2n+1,2n+2,2n+2), & \text{if } i = 2n+1, \\ (4n-i+3,4n-i+5,4n-i+4), & \text{if } 2n+2 \le i \le 4n, \\ (2,5,3), & \text{if } i = 4n+1. \end{cases}\]

Therefore the set W resolves all the vertices in \(V(F_3[n]) \setminus W\). Thus \(\dim(F_3[n]) \leq 3\). Now we show that \(\dim(F_3[n]) \geq 3\). For this we show that there does not exists any resolving set W' with two vertices. Let \(A = \{a_1, a_2, a_3, a_4, a_5, a_6\}\), \(B = \{z_1, z_2, z_3, z_4, z_5, z_6\}\), \(C = \{x_1, x_2, \cdots, x_{4n+1}\}\), \(D = \{b_1, b_2, \cdots, b_{4n+1}\}\), \(E = \{c_1, c_2, \cdots, c_{4n+1}\}\) and \(F = \{y_1, y_2, \cdots, y_{4n+1}\}\) be the sets of vertices of \(F_3[n]\). Then there are following cases:

Case 1. If both vertices of W' are in the set of vertices C, then the vertices of A and D have the same representation. Therefore W' is not a resolving set of \(F_3[n]\).

Case 2. If both vertices of W' are in the set of vertices D, then the vertices of B and C have the same representation. Therefore W' is not a resolving set of \(F_3[n]\).

Case 3. The vertices of set A have same distance from the vertices of B. Therefore the resolving set is not the subset of A or B.

Case 4. If both vertices of W' are in the set of vertices F, then the vertices of A and E have the same representation. Therefore W' is not a resolving set of \(F_3[n]\).

Case 5. If both vertices of W' are in the set of vertices E, then the vertices of B and F have the same representation. Therefore W' is not a resolving set of \(F_3[n]\).

Thus, in every case we get a contradiction. From above cases, we conclude that there is no resolving set W' with exactly two vertices of \(F_3[n]\). Thus the metric dimension of \(F_3[n]\) is 3. This completes the proof.

Figure 4. The Graph \(F_4[n]\).

Theorem 2.4. The metric dimension of fullerene graph F4[n] is 3.

Proof. Let W = {a3, a7, a8} ⊂ V (F4[n]). We need to show that W is a resolving set of F4[n]. First we give the representation of vertices of F4[n] \ W with respect to W.

\[r(a_1|W) = (2, 4n + 2, 4n + 2), \quad r(a_2|W) = (1, 4n + 1, 4n + 1), \quad r(a_4|W) = (1, 4n + 1, 4n),\]
\(r(a_5|W) = (4n + 2, 2, 2), \qquad r(a_6|W) = (4n + 1, 1, 1).\)

The representation of vertices of upper half of the fullerene graph F4[n] is given below:

\[r(x_i|W) = \begin{cases} (3,4n+i,4n+i+1), & \text{if } i = 1, \\ (i,4n-i+2,4n-i+3), & \text{if } 2 \le i \le 4n, \\ (4n+1,3,4), & \text{if } i = 4n+1. \end{cases}\]

The representation of middle vertices of the fullerene graph F4[n] is given below:

\[r(y_i|W) = (i, 4n - i, 4n - i + 1), 1 \le i \le 4n - 1,\]
\[r(z_i|W) = (i + 1, 4n - i + 1, 4n - i), 1 \le i \le 4n - 1.\]

The representation of vertices of lower half of the fullerene graph F4[n] is given below:

\[r(b_i|W) = \begin{cases} (3,4n+2,4n+1), & \text{if } i = 1, \\ (i+1,4n-i+3,4n-i+2), & \text{if } 2 \le i \le 4n, \\ (4n+2,3,3), & \text{if } i = 4n+1. \end{cases}\]

All vertices of V (F4[n]) \ W can be resolved with respect to W. Thus W is a resolving set of F4[n] and dim(F4[n]) ≤ 3.

On the other hand, we show that dim(F4[n]) ≥ 3 by proving that there is no resolving set W⁰ with cardinality 2. Suppose on contrary that dim(F4[n]) = 2 and W⁰ is a resolving set of F4[n] with |W⁰ | = 2. Let A = {a1, a2, ·, a8}, B = {x1, x2, · · · , x4n+1}, C = {y1, y2, · · · , y4n+1}, D = {z1, z2, · · · , z4n+1} and E = {b1, b2, · · · , b4n+1} be the sets of vertices of F4[n]. The pairs of vertices a1, a³ and a5, a⁷ have the same distance with the vertices of set B. The pairs of vertices a2, a⁴ and a6, a⁸ have the same distance with the vertices of set C. The pairs of vertices a2, a³ and a6, a⁷ have the same distance with the vertices of set D. Similarly, The pairs of vertices a1, a⁴ and a5, a⁸ have the same distance with the vertices of set C. Therefore, there is no a resolving set W⁰ with cardinality 2 of F4[n]. Thus dim(F4[n]) = 3. This completes the proof.

3. Metric dimension of (4,6)-fullerene graphs

Suppose G1[n], G2[n] and G3[n] are depicted in Figures 5-7 with order 8n, 8n+4 and 12n+12 respectively. In this subsection we find the metric dimension of G1[n], G2[n] and G3[n] fullerene graphs.

Theorem 3.1. The metric dimension of fullerene graph G1[n] is 3 for n ≥ 2.

Figure 5. The Graph \(G_1[n]\).

Proof. For a set \(W = \{x_1, y_1, x_{4n}\} \subset V(G_1[n])\), we need to show that W is a resolving set of \(G_1[n]\). First we show that \(\dim(G_1[n]) \neq 2\). There are following cases:

Case 1. If both vertices are in the upper half of \(G_1[n]\) and the resolving set is \(W' = \{x_s, x_t\}\), \(1 \le s \le t \le 4n\). Then the representations of \(x_i\) and \(y_{i+1}\), \(2n+1 \le i \le 4n-1\) are the same. Similarly the representations of \(x_{i+1}\) and \(y_i\), \(1 \le i \le 2n-1\) are the same. Therefore the resolving set of \(G_1[n]\) is not a subset of \(\{x_1, x_2, \cdots, x_{4n}\}\).

Case 2. If both vertices are in the lower half of \(G_1[n]\) and the resolving set is \(W' = \{y_s, y_t\}\), \(1 \le s \le t \le 4n\). Then the representations of \(x_{i+1}\) and \(y_i\), \(2n+1 \le i \le 4n-1\) are the same. Similarly the representations of \(x_i\) and \(y_{i+1}\), \(1 \le i \le 2n-1\) are the same. Therefore the resolving set is not a subset of \(\{y_1, y_2, \cdots, y_{4n}\}\).

Case 3. If one vertex belongs to the set of vertices \(\{x_1, x_2, \dots, x_{4n}\}\) and other is in the set of vertices \(\{y_1, y_2, \dots, y_{4n}\}\). Without loss of generality, we can suppose that the resolving set is \(W' = \{x_s, y_t\}, 1 \le s \le 4n\) and \(1 \le t \le 4n\).

If s = t, then the representation of pairs of vertices \(x_{s+1}, x_{s-1}\) and \(y_{t-1}, y_{t+1}\) are the same.

If s < t, then the representation of \(x_i\), i > s and \(y_j\), j < 4n are the same.

If s > t, then the representation of \(x_i\), i < 4n and \(y_j\), j > t are the same.

Thus, in every subcase we get a contradiction. From above cases, we conclude that there is no resolving set W' with |W'|=2. Thus \(\dim(G_1[n])\geq 3\). Now we show that \(\dim(G_1[n])\leq 3\). For this purpose we give the representation of the vertices in \(V(G_1[n])\setminus W\) with respect to W. The representation of vertices of upper half of the fullerene graph \(G_1[n]\) is given below:

\[r(x_i|W) = \begin{cases} (i-1, i, i), & \text{if } 2 \le i \le 2n, \\ (4n-i+1, 4n-i+2, 4n-i), & \text{if } 2n+1 \le i \le 4n-1. \end{cases}\]

The representation of vertices of lower half of the fullerene graph \(G_1[n]\) is given below:

\[r(y_i|W) = \begin{cases} (i, i-1, i+1), & \text{if } 2 \le i \le 2n, \\ (4n-i+2, 4n-i+1, 4n-i+1), & \text{if } 2n+1 \le i \le 4n. \end{cases}\]

This implies that all vertices of \(V(G_1[n]) \setminus W\) can be resolved with respect to W. Thus W is a resolving set of \(G_1[n]\). Therefore \(\dim(G_1[n]) = 3\) for \(n \ge 2\). This completes the proof.

Figure 6. The Graph \(G_2[n]\).

Theorem 3.2. The metric dimension of fullerene graph \(G_2[n]\) is 3.

Proof. Let \(W = \{x_1, y_1, x_{4n+2}\} \subset V(G_2[n])\). We show that W is a resolving set of \(G_2[n]\). First we give the representation of vertices in \(V(G_2[n]) \setminus W\) with respect to W. The representation of vertices of upper half of the fullerene graph \(G_2[n]\) is given by:

\[r(x_i|W) = \begin{cases} (i-1,i,i), & \text{if } 2 \le i \le 2n+1, \\ (4n-i+3,4n-i+4,4n-i+2), & \text{if } 2n+2 \le i \le 4n+1. \end{cases}\]

The representation of vertices of lower half of the fullerene graph \(G_2[n]\) is given by:

\[r(y_i|W) = \begin{cases} (i, i-1, i+1), & \text{if } 2 \le i \le 2n+1, \\ (4n-i+4, 4n-i+3, 4n-i+3), & \text{if } 2n+2 \le i \le 4n+2. \end{cases}\]

This implies that W is a resolving set of \(G_2[n]\) and \(\dim(G_2[n]) \leq 3\). Now we show that \(\dim(G_2[n]) \geq 3\) by proving that W' is a resolving set of \(G_2[n]\) with |W'| = 2. There are following possibilities:

Case 1. If both vertices are in the upper half of \(G_2[n]\) and the resolving set is \(W' = \{x_s, x_t\}\), \(1 \le s \le t \le 4n\). Then the representation of \(x_i\) and \(y_{i+1}\), \(2n+2 \le i \le 4n-1\) is the same. Similarly the representation of \(x_{i+1}\) and \(y_i\), \(1 \le i \le 2n\) is the same. Therefore the resolving set of \(G_2[n]\) is not a subset of \(\{x_1, x_2, \cdots, x_{4n}\}\).

Case 2. If both vertices are in the lower half of \(G_1[n]\) and the resolving set is \(W' = \{y_s, y_t\}\), \(1 \le s \le t \le 4n\). Then the representation of \(x_{i+1}\) and \(y_i\), \(2n+2 \le i \le 4n-1\) is the same. Similarly the representation of \(x_i\) and \(y_{i+1}\), \(1 \le i \le 2n\) is the same. Therefore the resolving set of \(G_2[n]\) is not a subset of \(G_2[n]\) is not a subset of \(G_2[n]\).

Case 3. If one vertex belongs to the set of vertices \(\{x_1, x_2, \dots, x_{4n}\}\) and other is in the set of vertices \(\{y_1, y_2, \dots, y_{4n}\}\). Without loss of generality, we can suppose that the resolving set of \(G_2[n]\) is \(W' = \{x_s, y_t\}\), \(1 \le s \le 4n\) and \(1 \le t \le 4n\).

If s = t, then the representation of pair of vertices \(x_{s+1}, x_{s-1}\) and \(y_{t-1}, y_{t+1}\) is the same.

If s < t, then the representation of \(x_i\), i > s and \(y_i\), j < 4n is the same.

If s > t, then the representation of \(x_i\), i < 4n and \(y_j\), j > t is the same.

From above cases, we conclude that there is no resolving set W' for \(G_2[n]\) with |W'|=2. Thus \(\dim(G_2[n])=3\). This completes the proof.

Figure 7. The Graph \(G_3[n]\).

Theorem 3.3. The metric dimension of fullerene graph \(G_3[n]\) is 3.

Proof. Let \(\{x_1, y_1, a_1, b_1, c_1, d_1\}\) be the set of outer vertices of \(G_3[n]\). The vertex \(x_1\) and \(y_1\) have the same distance from other vertices and \(a_1\) and \(b_1\) have the same distance from other vertices of \(G_3[n]\). Similarly \(c_1\) and \(d_1\) have the same distance from other vertices of \(G_3[n]\). Thus any metric basis will contain either \(x_1\) or \(y_1\), \(a_1\) or \(b_1\) and \(c_1\) or \(d_1\). There are 6 boundary vertices in \(G_3[n]\). Hence any metric basis of \(G_3[n]\) should contain at least 3 nodes of \(G_3[n]\). Let \(W = \{x_1, a_1, c_1\} \subset V(G_3[n])\), we need to show that W is a resolving set of \(G_3[n]\). Then the representation of vertices in \(V(G_3[n]) \setminus W\) with respect to W for \(n \geq 2\) is given by:

\[r(x_i|W) = (i-1, i+1, i+1), \quad \text{if} \quad 2 \le i \le 2n+2,\] \[r(y_i|W) = (i, i+2, i), \quad \text{if} \quad 1 \le i \le 2n+2,\] \[r(a_i|W) = (i+1, i-1, i+1), \quad \text{if} \quad 2 \le i \le 2n+2,\] \[r(b_i|W) = (i, i, i+2), \quad \text{if} \quad 1 \le i \le 2n+2,\] \[r(c_i|W) = (i+1, i+1, i-1), \quad \text{if} \quad 2 \le i \le 2n+2,\] \[r(d_i|W) = (i+2, i, i), \quad \text{if} \quad 1 \le i \le 2n+2.\]

The representation of vertices of \(V(G_3[n]) \setminus W\) with respect to W for n = 1 is given by:

\[r(x_i|W) = \begin{cases} (i-1,i+1,i+1), & \text{if } 2 \le i \le 2n+1, \\ (i-1,i,i), & \text{if } i = 2n+2. \end{cases}\] \[r(y_i|W) = \begin{cases} (i,i+2,i), & \text{if } 1 \le i \le 2n+1, \\ (i,i+1,i), & \text{if } i = 2n+2. \end{cases}\] \[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

Hence there are no two vertices having the same representations. Thus W = {x1, c1, a1} is a resolving set of G3[n]. Therefore dim(G3[n]) = 3. This completes the proof.

4. Conclusion and open problems

In this paper, we considered some (3, 6)-fullerene and (4, 6)-fullerene graphs and computed the metric dimension for these fullerene graphs. All (3, 6)-fullerene and (4, 6)-fullerene graphs considered in this paper have metric dimension 3. It will be interesting to prove or disprove the following statement:

"All (3, 6)-fullerene and (4, 6)-fullerene graphs have metric dimension 3."

Acknowledgement

This research is supported by the Higher Education Commission of Pakistan under grant No. 20-3067/NRPU /R&D/HEC/12

References

• [1] A.R. Ashrafi and Z. Mehranian, Topological study of (3, 6)− and (4, 6)−fullerenes, Topological Modelling of Nanostructures and Extended Systems, Springer Netherlands, (2013), 487–510.
• [2] R.C. Brigham, G. Chartrand, R.D. Dutton and P. Zhang, Resolving domination in graphs, Math. Bohem. 128 (1) (2003), 25–36.
• [3] G. Chartrand, L. Eroh, M.A. Johnson and O.R. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math. 105 (2000), 99–113.
• [4] G. Chartrand, C. Poisson and P. Zhang, Resolvability and the upper dimension of graphs, Comput. Math. Appl. 39 (2000), 19–28.
• [5] G. Chartrand, E. Salehi and P. Zhang, The partition dimension of a graph, Aequationes Math. 59 (2000), 45–54.
• [6] P.W. Fowler and D.E. Manolopoulos, An Atlas of Fullerenes, Oxford Univ Press Oxford, (1995).
• [7] F. Harary and R.A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976), 191– 195.
• [8] H.W. Kroto, J.R. Heath, S.C. OBrien, R.F. Curl and R.E. Smalley, C60: buckminsterfullerene, Nature 318 (1985), 162–163.
• [9] S. Khuller, B. Raghavachari and A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math. 70 (3) (1996), 217–229.

• [10] F. Koorepazan-Moftakhar, A.R. Ashrafi and Z. Mehranian, Automorphism group and fixing number of (3, 6)- and (4, 6)−fullerene graphs, Electron. Notes Discrete Math. 45 (2014), 113–120.
• [11] F. Okamoto, B. Phinezyn and P. Zhang, The local metric dimension of a graph, Math. Bohem. 135 (3) (2010), 239–255.
• [12] B. Rajan, I. Rajasingh, M.C. Monica and P. Manuel, Metric dimension of enhanced hypercube networks, J. Combin. Math. Combin. Comput. 67 (2008), 5–15.
• [13] A. Sebo and E. Tannier, On metric generators of graphs, ¨ Math. Oper. Res. 29 (2) (2004), 383–393.
• [14] H.M.A. Siddiqui and M. Imran, Computation of metric dimension and partition dimension of Nanotubes, Journal of Computational and Theoretical Nanoscience 12 (2) (2015), 199–203.
• [15] H.M.A. Siddiqui and M. Imran, Computing metric and partition dimension of 2−Dimensional lattices of certain Nanotubes, Journal of Computational and Theoretical Nanoscience 11 (12) (2014), 2419–2423.
• [16] P.J. Slater, Leaves of trees, Congr. Numer. 14 (1975), 549–559.