On Commutative Characterization of Graph Operation with Respect to Metric Dimension

1 Introduction

Let ܩ be a finite and simple connected graph. The vertex and edge sets of graph ܩ are denoted by ܸሺܩሻ and ܧሺܩሻ, respectively. The distance between vertices v and w in ܩ, denoted by ݀ሺݒ, ݓሻ, is the length of the shortest path between v and w. Let ܹ ൌ ሼݓଵ, ݓଶ,…,ݓሽ ⊆ ܸሺܩሻ be the ordered set and v a vertex on graph ܩ. The representation of v with respect to W is an ordered m-tuple, ݎሺݒ|ܹሻ ൌ ሺ݀ሺݒ, ݓଵሻ, ݀ሺݒ, ݓଶሻ,…,݀ሺݒ, ݓሻሻ. The set ܹ is called a resolving set of ܩ if all vertices of ܩ have distinct representations with respect to W. A minimum resolving set of graph ܩ is called a basis of ܩ. The cardinality of a basis is called the metric dimension of ܩ, denoted by dimሺܩሻ. Chartrand, et al. [1] characterized the metric dimension of certain graphs, i.e. dimሺܩሻ ൌ 1 if and only if ܩൌܲ and dimሺܩሻ ൌ݊െ1 if and only if ܩൌܭ for graph ܩ of order n ≥ 2.

Received May 10th, 2016, 1st Revision January 23rd, 2017, 2nd Revision January 26th, 2017, Accepted for publication March 3rd, 2017.

Copyright © 2017 Published by ITB Journal Publisher, ISSN: 2337-5760, DOI: 10.5614/j.math.fund.sci.2017.49.2.5

Saputro, et al. [2] obtained the metric dimension of the comb product of graph G o H. This product is a special case of the rooted product graph, which has been defined by Godsil and McKay in [3]. Let G and H be two connected graphs and o be a vertex of H. The comb product between G and H, denoted by G o H, is a graph obtained by taking one copy of G and |V(G)| copies of H and grafting the i-th copy of H at the vertex o to the i-th vertex of G.

Theorem 1. [2] Let G and H be connected graphs of order at least 2. If |V(G)| = m and H is not a path, then:

\[\dim(GoH) = \begin{cases} m \ (dim(H) - 1), \ \text{if there exists a basis of H containing o} \\ m \ dim(H), \ \text{otherwise} \end{cases}\]

Frucht and Harary [4] provide the definition of the corona product. Let G be a connected graph of order n and H (not necessarily connected) be a graph of order at least two. The graph G corona H, denoted by \(G \odot H\), is a graph that is obtained by taking n copies of graphs \(H_1, H_2, ..., H_n\) of H, and connecting the i-th vertex of G to all vertices of \(H_i\). The metric dimension of the corona product of two graphs has been determined by Iswadi, et al. [5].

Theorem 2. [4] Let G be a connected graph and H be a graph of order at least 2. Then:

\[\dim(G \odot H) = \begin{cases} |G| \dim(H), & \text{if } H \text{ contains a dominant } vertex \\ |G| \dim(K_1 + H), & \text{otherwise} \end{cases}\]

In this paper, we discuss the metric dimension of the generalized comb product and the generalized corona product of graphs. We also discuss commutative characterization with respect to the metric dimension of the comb product and the corona product. The definition of the comb product, the rooted product and the corona product will be generalized by the k-comb product, the k-rooted product and the k-corona product, respectively. The generalized corona product includes the corona product of a graph and a sequence of graphs. The generalized definitions will be given in the next section.

2 Generalized Comb and Corona Product Graphs

An operation * defined on two graphs is said to be commutative if \(A*B \cong B*A\)for every graph A and B. An operation * defined on two graphs G and H is said to be commutative with respect to the metric dimension if dim(G * H) =\(\dim(H * G)\), denoted by \((G * H) \cong \dim(H * G)\).

Let G and H be connected graphs, n be the order of G and o be a vertex of H. The k-comb product of G and H, denoted by \(Go_kH\), is a graph obtained from G and H by taking one copy of G and nk copies of H, i.e. \(H_{11}\), \(H_{12}\), \(H_{13}\), ..., \(H_{1lk}\), \(H_{21}\), \(H_{22}\), \(H_{23}\), ..., \(H_{2k}\), ..., \(H_{n1}\), \(H_{n2}\), \(H_{n3}\), ..., \(H_{nk}\) and grafting the vertex \(o_{ij}\), j=1,2,3, ..., k with the i-th vertex of G. In graph \(Go_kH\), the vertex \(o_{is}=o_i\) for s=1,2, ..., k, and \(Go_lH=GoH\). Hence, the k-comb product can be considered the generalized comb product.

Let G be a connected labeled graph of order n and \(\mathcal{H}\) be a sequence of n rooted graphs \(H_1\), \(H_2\), \(H_3\), ..., \(H_m\). The k-rooted product of G and \(\mathcal{H}\), denoted by \(G \circ_k \mathcal{H}\), is a graph obtained from G and \(\mathcal{H}\) by taking one copy of G and G copies of G, i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e. G i.e.

Rodriguez, et al. [6] defined the corona product of two graphs as follows. Let G be a connected labeled graph of order n and \(\mathcal{H}\) be a sequence of n graphs \(H_1\), \(H_2\), \(H_3\), ..., \(H_n\). The corona product of G and \(\mathcal{H}\), denoted by \(G \odot \mathcal{H}\), is a graph obtained from G and \(\mathcal{H}\) by taking one copy of G and K copies of \(\mathcal{H}\), i.e. \(H_{II}\), \(H_{I2}\), \(H_{I3}\), ..., \(H_{Ik}\), \(H_{2I}\), \(H_{22}\), \(H_{23}\), ..., \(H_{2k}\), ..., \(H_{nI}\), \(H_{n2}\), \(H_{n3}\), ..., \(H_{nk}\) and joining by an edge each vertex of \(H_{ii}\), i = 1, 2, 3, ..., K with the i-th vertex of G.

Let G be a connected graph of order n and H be a graph. The k-corona product of G and H, denoted by \(G \odot_k \mathcal{H}\), is a graph obtained from G and H by taking one copy of G and nk copies of H, i.e. \(H_{II}\), \(H_{I2}\), \(H_{I3}\), ..., \(H_{Ik}\), \(H_{2I}\), \(H_{22}\), \(H_{23}\), ..., \(H_{2k}\), ..., \(H_{nl}\), \(H_{n2}\), \(H_{n3}\), ..., \(H_{nk}\), and joining by an edge each vertex of \(H_{ij}\), \(H_{n2}\), \(H_{n3}\), ..., \(H_{nk}\), with the \(H_{n2}\)-th vertex of \(H_{n3}\). If \(H_{n2}\) is a large each vertex of \(H_{n3}\). Hence, the \(H_{n3}\)-corona product can be considered the generalized corona product.

Let G be a connected labeled graph of order n and \(\mathcal{H}\) be a sequence of n graphs \(H_1, H_2, H_3, ..., H_n\). The k-corona product of G and \(\mathcal{H}\), denoted by \(G \odot_k \mathcal{H}\), is a graph obtained from G and \(\mathcal{H}\) by taking one copy of G and k copies of \(\mathcal{H}\), i.e. \(H_{11}, H_{12}, H_{13}, ..., H_{1k}, H_{2l}, H_{22}, H_{23}, ..., H_{2k}, ..., H_{nl}, H_{n2}, H_{n3}, ..., H_{nk}\) and joining by an edge each vertex of \(H_{ij}\), j = 1, 2, 3, ..., k with the i-th vertex of G. If k = 1, then \(G \odot_k \mathcal{H} = G \odot \mathcal{H}\).

3 Metric Dimension of Generalized Comb Product Graphs

The metric dimension of the generalized comb product (including the rooted product) and the corona product graphs are presented in the next theorems. We first present the metric dimension of the rooted product of graph G and sequence of graphs \(\mathcal{H}\) as follows.

Theorem 3. Let G be a labelled connected graph of order \(n \ge 2\) and \(\mathcal{H}\) a sequence of n connected non path rooted graphs of order at least two, namely \(H_1\), \(H_2\), \(H_3\), ..., \(H_n\). If \(o_i\) is the root of \(H_i\) for every i = 1, 2,...,n, then:

\[\begin{aligned} \dim(G \circ \mathcal{H}) &= \sum_{i=1}^{n} (\dim(H_i)) - \alpha_i), \\ \text{where } \alpha_i &= \begin{cases} 1, if \ o_i \ belongs \ to \ a \ basis \ of \ H_i \\ 0, otherwise \end{cases}. \end{aligned}\]

Proof. Let G be a labeled graph on n vertices and \(\mathcal{H}\) be a sequence of n connected rooted non path graphs of order at least two \(H_1, H_2, H_3, ..., H_n\). Let \(o_i\)be the root of \(H_i\) and \(B_i\) a basis of \(H_i\), for every i = 1, 2, ..., n. Choose \(W = \bigcup_{i=1}^{n} \{B_i - \{o_i\}\}, \text{ so } |W| = \sum_{i=1}^{n} (\dim(H_i)) - \alpha_i),\)

where \[\alpha_i = \begin{cases} 1, if & o_i \text{ belongs to a basis of } H_i \\ 0, \text{ otherwise} \end{cases}\].

Suppose that x, y are any two distinct vertices in G o \(\mathcal{H}\). Then there are four possibilities:

• (a) x,y are rooted vertices.
• (b) x, y belong to \(H_i, x, y \neq o_i\).
• (c) x belongs to \(H_i\) and y is a rooted vertex.
• (d) x belongs to \(H_i\) and y belongs to \(H_i\), \(x \neq o_i\), \(y \neq o_i\) \(i \neq j\).

We consider all possibilities:

• (a) Suppose x,y are rooted vertices. Let \(x = o_i\), \(y = o_j\). We get \(d(o_i, o_j) \neq 0\)\(d(o_i, o_i)\), so \(d(o_i, v) \neq d(o_i, v)\) for every \(v \in B_i\) and \(r(x|W) \neq r(y, W)\).
• (b) Suppose x and y belong to \(H_i\). Let \(x = x_i, y = y_i\). There are two possibilities, namely \(r(x_i|\{B_i - \{o_i\}\}) \neq r(y_i|\{B_i - \{o_i\}\})\) or \(r(x_i|\{B_i - \{o_i\}\})\)\(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\)If \(r(x_i | \{B_i - \{o_i\}\}) \neq r(y_i | \{B_i - \{o_i\}\})\), then \(r(x_i | W) \neq r(y_i | W)\). If \(r(x_i|\{B_i - \{o_i\}\}) = r(y_i|\{B_i - \{o_i\}\})\), then \(d(x_i|o_i) \neq d(y_i|o_i)\), so \(r(x_i|\{B_i o - \{o_i\}\}) = r(y_i|\{B_i - \{o_i\}\})\). For \(i \neq j\), we get \(r(x_i|W) \neq j\)\(r(y_i|W)\).
• (c) Suppose x belongs to \(H_i\) and y is a rooted vertex. This means that y belongs to G. There are two possibilities, namely \(x = o_i\) or \(x \neq o_i\). For \(x = o_i\), because \(d(o_i, o_i) \neq d(y, o_i)\) and \(o_i \in B_i\), we get \(r(x|B_i \cup B_i - \{o_i, o_i\}) \neq\)\(r(y|B_i \cup B_i - \{o_i, o_i\})\) for \(i \neq j\), so \(r(x|W) \neq r(y|W)\). For \(x \neq o_i\), without loss of generality, let \(x = o_i\), \(i \neq j\). We get \(r(x|B_i \cup B_i -\)\(\{o_i, o_i\}\) \neq r(y|B_i \cup B_i - \{o_i, o_i\}), \text{ so } r(x|W) \neq r(y|W).\)
• (d) If x belongs to \(H_i\) and y belongs to \(H_j\), \(i \neq j\), then \(r(x|B_i \cup B_j \{o_i, o_i\}) \neq\)\(r(y|B_i \cup B_i - \{o_i, o_i\})\). We get \(r(x|W) \neq r(y|W)\).

Hence, we have \(W = \bigcup_{i=1}^n \{B_i - \{o_i\}\}\) is a resolving set of \(G \circ \mathcal{H}\). We now show that W is minimal. Suppose that S is any set such that \(S \subseteq V(G \circ \mathcal{H})\) and |S| < |W|. Since |S| < |W|, then there is i such that S contains at most \(|B_i - \{o_i\}| - 1\) elements of \(H_i\). As a result, there are two vertices in \(H_i\) that have the same representation with respect to S. Thus, S is not a resolving set. Consequently, W is a basis of \(G \circ \mathcal{H}\) and \(\dim(G \circ \mathcal{H}) = \sum_{i=1}^n (\dim(H_i) - \alpha_i)\) where:

\[\alpha_i = \begin{cases} 1, if & o_i \text{ belongs to a basis of } H_i \\ 0, otherwise \end{cases}.\]

In the next theorem, we give the metric dimension of the generalized k-comb product of graphs G and H.

Theorem 4. Let G be a connected graph of order n, H is a non path graph of order at least two, and o is grafting vertex of G \(o_k\) H. Then:

\[\dim(G \ o_k \ H) = \begin{cases} nk(\dim(H) - 1) \text{, if there exists a basis of $H$ containing o} \\ nk \dim(H) \text{,} & \text{otherwise} \end{cases}\]

Proof. Let G be a connected graph of order n, H a non path graph of order at least two, and o a grafting vertex of G o_k H. Consider nk copies of H are \(H_{11}\), \(H_{12}\), \(H_{13}\), ..., \(H_{1k}\), \(H_{21}\), \(H_{22}\), \(H_{23}\), ..., \(H_{2k}\), ..., \(H_{n1}\), \(H_{n2}\), \(H_{n3}\), ..., \(H_{nk}\). Let B be a basis of H, \(B_{ij}\) be a basis \(H_{ij}\) and \(o_{ij}\) be a copy of o in \(H_{ij}\), i = 1, 2, 3, ..., n; j = 1, 2, 3, ..., k. We get \(o_{ij} = o_i\) for j = 1, 2, 3, ..., k and \(|B_{ij}| = |B| = \dim(H)\). There are two possibilities, namely there is a basis of H containing o and no basis of H containing o.

We consider the first case. Suppose there is a basis of H containing o. Choose \(W = \bigcup_{i=1}^{n} \bigcup_{j=1}^{k} \{B_{ij} - \{o_i\}\}\). We get |W| = nk (dim(H) - 1). Suppose x, y are any two distinct vertices in \(G \circ_k H\). Then there are five possibilities, namely:

• (a) x and y belong to G.
• (b) x and y belong to \(H_{ij} \cong H_i\); \(x, y \neq o_i\).
• (c) x belongs to G and y belongs to \(H_{ij} \cong H_i\); \(y \neq o_i\).
• (d) x belongs to \(H_{ij}\) and y belongs to \(H_{il}\), where \(j \neq l\); \(x, y \neq o_i\).
• (e) x belongs to \(H_{ij}\) and y belongs to \(H_{kl}\) for \(i \neq k\); \(x \neq o_i\), \(y \neq o_k\).

We consider all possibilities:

(a) Suppose x and y belong to G. Let \(x = o_i\) and \(y = o_j\). Then \(d(o_i o_j) \neq d(o_i, o_i)\) so \((d(o_i, v) \neq d(o_j, v))\) for every \(\in B_{il}\), l = 1, 2, ..., k. Consequently, \(r(x|W) \neq r(y, W)\).

• (b) Suppose x and y belong to \(H_{ij} \cong H_i\); \(x, y \neq o_i\). Let \(x = x_i, y = y_i\). Hence, there are two possibilities, \(r(x_i|\{B_{ij}-\{o_i\}\}) \neq r(y_i|\{B_{ij}-\{o_i\}\})\) or \(r(x_i|\{B_{i,i} - \{o_i\}\}) = r(y_i|\{B_{i,i} - \{o_i\}\}).\) For \(r(x_i|\{B_{i,i} - \{o_i\}\}) \neq\)\(r(y_i | \{B_{ij} - \{o_i\}\})\), we get \(r(x_i | W) \neq r(y_i | W)\). Suppose \(r(x_i | \{B_{ij} - \{o_i\}\})\)\(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\)) = \(r(y_i | \{B_{ij} - \{o_i\}\})\). Since \(B_{ij}\) is a basis of \(H_{ij}\) and \(o_i \in B_{ij}\) then \(d(x_i|o_i) \neq d(y_i|o_i)\). Hence, \(r(x_i|\{B_{kl} - \{o_k\}\}) = r(y_i|\{B_{kl} - \{o_k\}\})\) for \(i \neq k\). Therefore \(r(x_i|W) \neq r(y_i|W)\).
• (c) Suppose x belongs to G and y belongs to \(H_{ij} \cong H_i, y \neq o_i\). There are two possibilities, namely \(x = o_i\) and \(x \neq o_i\). Let \(x = o_i\). Since \(d(o_i, o_i) \neq d(y, o_i)\)and \(o_i \in B_{ij}\), then \(r(x|B_{ij} \cup B_{kl} - \{o_i, o_k\}) \neq r(y|B_{ij} \cup B_{kl} - \{o_i, o_k\})\)for \(i \neq k\). Therefore \(r(x|W) \neq r(y|W)\). Now, let \(x \neq o_i\). Without loss of generality, let \(x = o_k\) where \(\neq k\). Then, \(r(x|B_{ij} \cup B_{kl} - \{o_i, o_k\}) \neq\)\(r(y|B_{ij} \cup B_{kl} - \{o_i, o_k\})\). Hence, \(r(x|W) \neq r(y|W)\).
• (d) Suppose x belongs to \(H_{ij}\) and y belongs to \(H_{il}\), where \(j \neq l\); \(x, y \neq o_i\). Then, \(d(x,s) = d(x,o_i) + d(o_i,s), \forall s \in B_{il}\) and \(d(y,s_r) = d(x,u_r)\), where \(s_r\) is r-th element of \(B_{il}\) and \(u_r\) is the r-th element of \(B_{ij}\). Consequently, \(r(x|B_{ij} \cup B_{kl} - \{o_i, o_k\}) \neq r(y|B_{ij} \cup B_{kl} - \{o_i, o_k\})\). So \(r(x|W) \neq r(y|W)\).
• (e) Suppose x belongs to \(H_{ij}\) and y belongs to \(H_{kl}\) for \(i \neq k, x \neq o_i, y \neq o_k\). By the same reasoning as in the case x belongs to \(H_{ij}\) and y belongs to \(H_{il}\), where \(\neq l\), we get \(r(x|W) \neq r(y|W)\).

Hence, we have \(W = \bigcup_{i=1}^n \bigcup_{j=1}^k \{B_{ij} - \{o_i\}\}\\) is a resolving set of \(Go_kH\). We now show that W is minimal. Suppose that S is any set such that \(S \subseteq\)\(V(G \circ_k H)\) and |S| < |W|. Then, S contains at most \(|B_{ij}| - 2\) elements of \(H_{ij}\) for some index i. As a result, there are two vertices of \(H_{ij}\) that have the same representation with respect to S. Thus S is not a resolving set. Consequently, W is a basis of \(G \circ_k H\) and:

\[\dim (Go_k H) = nk(\dim(h) - 1.\]

Now we consider the second case, where there is no basis of H containing o. Choose \(W = \bigcup_{i=1}^n \bigcup_{i=1}^k \{B_{ii}\}\). Hence, \(|W| = nk (\dim(H))\). Take any two distinct vertices x, y in \(G \circ_k H\). There are five possibilities, namely:

• (a) x and y belong to G.
• (b) x and y belong to \(H_{ij} \cong H_i\); \(x, y \neq o_i\).
• (c) x belongs to G and y belongs to \(H_{i,i} \cong H_i\), \(y \neq o_i\).
• (d) x belongs to \(H_{ij}\) and y belongs to \(H_{il}\), where \(j \neq l, x, y \neq o_i\).
• (e) x belongs to \(H_{ij}\) and y belongs to \(H_{kl}\) for \(i \neq k\), \(x \neq o_i\), \(y \neq o_k\).

By using the same technique as presented in the first case, it can be proved that \(W = \bigcup_{i=1}^{n} \bigcup_{j=1}^{k} \{B_{ij}\}\) is a basis of \(G \circ_k H\) and:

\[\dim(G \circ_k H) = (\dim(H)).\]

A more general result on the metric dimension of the generalized comb product of graphs is presented in the following theorem.

Theorem 5. Let G be a connected labelled graph of order n and \(\mathcal{H}\) be a sequence of n non path rooted graphs of order at least two, namely \(H_1\), \(H_2\), \(H_3\), ..., \(H_n\). Then \(\dim(G \circ_k \mathcal{H}) = k \sum_{i=1}^n (\dim(H_i) - \alpha_i)\), where

\[\alpha_i = \begin{cases} 1, & \text{if there is a basis of } H_i \text{ containing rooted vertex} \\ 0, & \text{otherwise} \end{cases}\]

Proof. Suppose k copies of \(\mathcal{H}\) are \(H_{11}\), \(H_{12}\), \(H_{13}\), ..., \(H_{1k}\), \(H_{21}\), \(H_{22}\), \(H_{23}\), ..., \(H_{2k}\), ...., \(H_{n1}\), \(H_{n2}\), \(H_{n3}\), ..., \(H_{nk}\). Let \(B_i\) be a basis of \(H_i\), \(B_{ij}\) a basis of \(H_{ij}\) and \(O_{ij}\) a rooted vertex of \(H_{ij}\), i = 1, 2, 3, ..., n; j = 1, 2, 3, ..., k. Hence, \(O_{ij} = O_i\) and \(|B_{ij}| = |B_i|\) for j = 1, 2, 3, ..., k. Choose \(W = \bigcup_{i=1}^n \bigcup_{j=1}^k \{B_{ij} - O_i\}\). Therefore, \(|W| = k \sum_{i=1}^n (\dim(H_i) - \alpha_i)\), where:

\[\alpha_i = \begin{cases} 1, & \text{if there is a basis of } H_i \text{ containng rooted vertex} \\ 0, & \text{otherwise} \end{cases}\]

Suppose x,y are any two distinct vertices in \(G \circ_k \mathcal{H}\). Then there are five possibilities, namely:

• (a) x and y belong to G.
• (b) x and y belong to \(H_{ij} \cong H_i, x, y \neq o_i\).
• (c) x belongs to G and y belongs to \(H_{ij} \cong H_i\), \(y \neq o_i\).
• (d) x belongs to \(H_{ij}\) and y belongs to \(H_{il}\), where \(j \neq l, x, y \neq o_i\).
• (e) x belongs to \(H_{ij}\) and y belongs to \(H_{kl}\) for \(i \neq k\), \(x \neq o_i\), \(y \neq o_k\).

By using the same technique as presented in the proof of Theorem 4, it can be shown that \(W = \bigcup_{i=1}^{n} \bigcup_{i=1}^{k} \{B_{i,i} - \{o_i\}\}\\) is a resolving set of \(G \circ_k \mathcal{H}\).

Now, we show that W is minimal. Suppose that S is any set such that \(S \subseteq V(G \circ_k \mathcal{H})\) and |S| < |W|. Then, S contains at most \(|B_{ij} - \{o_i\}| - 1\) elements of \(H_{ij}\) for some index i. As a result, there are two vertices of \(H_{ij}\) that have the same representation with respect to S. Thus, S is not a resolving set. Consequently, W is a basis of \(G \circ_k \mathcal{H}\) and \(\dim(G \circ_k \mathcal{H}) = k \sum_{i=1}^n (\dim(H_i) - \alpha_i)\), where:

\[\alpha_i = \begin{cases} 1, & \text{if there is a basis of } H_i \text{ containing rooted vertex} \\ 0, & \text{otherwise} \end{cases}.\]

4 Metric Dimension of Generalized Corona Product Graphs

Similar to the generalized comb product, the metric dimension of the generalized corona product of graphs is presented in this section. We start this section with the metric dimension of the corona product of graph G and sequence of graphs \(\mathcal{H}\) as follows.

Theorem 6. Let G be a connected labelled graph of order n and \(\mathcal{H}\) be a sequence of n rooted graphs. Then, \(\dim(G \odot \mathcal{H}) = \sum_{i=1}^{n} (\dim(K_1 + H_i) - \alpha_i)\), where:

\[\alpha_i = \begin{cases} 1, & \text{if there is a basis of } K_1 + H_i \text{ containing vertex of } K_1 \\ 0, & \text{otherwise} \end{cases}.\]

Proof. Let \(V(G) = \{v_1, v_2, ..., v_n\}\) and \(\mathcal{H}\) be a sequence of n rooted graphs, namely \(H_1\), \(H_2\), \(H_3\), ..., \(H_n\). Let B be a basis of H, and \(B_i\) a basis of \(\langle v_i \rangle + H_i\), i =1, 2, ..., n. Choose \(W = \bigcup_{i=1}^{n} (B_i - \{v_i\})\). Since, \(\langle v_i \rangle + H_i \cong K_1 + H, \forall i = 1, 2, ..., n\)1,2,..., n we have \(|W| = \sum_{i=1}^{n} (\dim(K_1 + H_i) - \alpha_i)\), where:

\[\alpha_i = \begin{cases} 1, & \textit{if there is a basis of } K_1 + H_i \textit{ containing vertex of } K_1 \\ 0, & \textit{otherwise} \end{cases}.\]

Suppose x,y are any two distinct vertices in \(G \odot_k H\). Then there are four possibilities, namely:

• (a) x and y belong to G.
• (b) x and y belong to \(H_i\).
• (c) x belongs to G and y belongs to \(H_i\).
• (d) x belongs to \(H_i\) and y belongs to \(H_i\) where \(i \neq j\).

We consider all possibilities:

• (a) Suppose x and y belong to G. Let \(x = v_k\), \(y = v_l\) where \(k \neq l\). Then \(d(v_k, v_l) \neq d(v_k, v_k)\). Consequently, \(d(v_k, v) \neq d(v_l, v)\) for every \(v \in H_k\). Therefore, \(r(v_k|W) \neq r(v_l|W)\).
• (b) If x and y belong to \(H_i\), then \(d(x, v_i) = d(y, v_i)\). Since \(B_i\) is a basis of \(\langle v_i \rangle + H_i\), we find \(d(x,s) \neq d(y,s)\) for some \(s \in (B_i - \{v_i\})\). Hence, \(r(x|W) \neq r(y|W)\).
• (c) Suppose x belongs to G and y belongs to \(H_i\). There are two possibilities, namely \(x = v_i\) or \(x = v_k\), where \(k \neq i\). For \(x = v_i\), we find \(d(v_i, u) \neq i\)\(d(y, u), \forall u \in H_k\), where \(k \neq i\). Hence, \(r(v_i|B_k - \{v_k\}) \neq r(y|B_k - \{v_k\})\). Consequently, \(r(v_i|W) \neq r(y|W)\). For \(x = v_k\), where \(k \neq i\), we find \(r(v_k|B_k - \{v_k\}) \neq d(y|B_k - \{v_k\})\). Consequently, \(r(v_k|W) \neq r(y|W)\).
• (d) If x belongs to \(H_i\) and y belongs to \(H_j\), where \(i \neq j\), then \(d(x, v_i) \neq j\)Consequently, \(r(x|(B_i \cup B_j - \{v_i, v_i\}) \neq r(y|(B_i \cup B_i - \{v_i, v_i\})))\)\(d(x, v_i)\).

\(\{v_i, v_j\}\)). Therefore, \(r(x|W) \neq r(y|W)\) and \(W = \bigcup_{i=1}^n (B_i - \{v_i\})\) is a resolving set of \(G \odot \mathcal{H}\).

Now, we show that W is minimal. Suppose S is any set such that \(S \subseteq V(G \odot \mathcal{H})\) and |S| < |W|. Then, S contains at most \(|B_j - \{v_j\}| - 1\) elements of \(\langle v_j \rangle + H_j\) for some index j. As a result, there are two distinct vertices of \(H_j\) that have the same representation with respect to S. Thus S is not a resolving set. Consequently, W is a basis of \(G \odot \mathcal{H}\) and \(\dim(G \odot \mathcal{H}) = \sum_{i=1}^n (\dim(K_1 + H_i) - \alpha_i)\), where:

\[\alpha_i = \begin{cases} 1, & \textit{if there is a basis of } K_1 + H_i \textit{ containing vertex of } K_1 \\ 0, & \textit{otherwise} \end{cases}.\]

In the next theorem, we give the metric dimension of the generalized k-corona product of graphs G and H.

Theorem 7. Let G be a connected graph of order n and H be a graph of order at least 2. If \(K_1 + H_i\) has a basis \(B_i\) such that there is no vertex x in \(H_i\) with \(r(x|B_i) = (2, 2, ..., 2)\), for every i. Then:

\[dim(G \odot_k H) = \begin{cases} kn \left( \dim(K_1 + H) - 1 \right), if \ basis \ of \ K_1 \ + \ H \ containing \ vertex \ of \ K_1 \\ kn \left( \dim(K_1 + H) \right), \end{cases}\] otherwise

Proof. Let \(V(G) = \{v_1, v_2, ..., v_n\}\) and nk copies of H be \(H_{11}, H_{12}, H_{13}, ..., H_{1k}, H_{21}, H_{22}, H_{23}, ..., H_{2k}, ..., H_{n1}, H_{n2}, H_{n3}, ..., H_{nk}\). Let B be a basis of H and \(H_{ij}\) a basis of \((v_i) + H_{ij}\), i = 1, 2, ..., n; i = 1, 2, ..., k. Then there are two possibilities, namely:

• (i) there is a basis of \(K_1 + H\) containing a vertex of \(K_1\).
• (ii) there is no basis of \(K_1 + H\) containing a vertex of \(K_1\).
• (I) Suppose there is a basis of \(K_1 + H\) containing a vertex of \(K_1\). Choose \(W = \bigcup_{i=1}^n \bigcup_{j=1}^k (B_{ij} \{v_i\})\). Since \(\langle v_i \rangle + H_{ij} \cong K_1 + H, \forall i = 1, 2, ..., n\); j = 1, 2, ..., k, then we have \(|W| = kn (\dim(K_1 + H) 1)\). Suppose x, y are any two distinct vertices in \(G \odot_k H\). Then there are five possibilities, namely:
  • (a) x and y belong to G.
  • (b) x and y belong to \(H_{ij} \cong H_i\).
  • (c) x belongs to G and y belongs to \(H_{ij} \cong H_i\).
  • (d) x belongs to \(H_{ij}\) and y belongs to \(H_{il}\), where \(j \neq l\).
  • (e) x belongs to \(H_{ij}\) and y belongs to \(H_{kl}\) for \(i \neq k\).

We consider all possibilities:

• (a) Suppose x and y belong to G. Let \(x = v_k\), \(y = v_l\), where \(k \neq l\). Then, \(d(v_k, v_l) \neq d(v_k, v_k)\). Hence, \(d(v_k, v) \neq d(v_l, v)\) for every \(v \in H_{k,l}\). Consequently, \(r(v_k|W) \neq r(v_l|W)\).
• (b) If x and y belong to \(H_{ij} \cong H_i\), then \(d(x, v_i) = d(y, v_i)\). Since \(B_{ij}\) is a basis of \(\langle v_i \rangle + H_{ij}\) and \(v_i \in B_{ij}\), then \(d(x,s) \neq d(y,s)\) for some \(s \in (B_{ij} - C_{ij})\)\(\{v_i\}\)). As a result, \(r(x|W) \neq r(y|W)\).
• (c) Suppose x belongs to G and y belongs to \(H_{ij} \cong H_i\). Then there are two possibilities, namely \(x = v_i\) or \(x = v_k\), where \(k \neq i\). For \(x = v_i\), this case is equal to the case x belongs to G and y belongs to \(H_{ij} \cong H_i\). For \(x = v_k\), where \(k \neq i\), we get \(d(v_k, v_i) \neq d(v_i, v_i)\). Consequently, \(d(v_k, v) \neq i\)\(d(v_i, v)\) for every \(v \in H_{ij}\). Therefore, \(r(v_k|W) \neq r(v_l|W)\).
• (d) Suppose x belongs to \(H_{ij}\) and y belongs to \(H_{il}\), where \(j \neq l\). Assume r(x|W) = r(y|W),then \(r(x|(B_{ij} - \{v_i\})) = r(y|(B_{il} - \{v_i\})) =\)(2, 2, ..., 2). However, this is contrary to the fact that \(B_{ij}\) and \(B_{il}\) are bases of \(\langle v_i \rangle + H_{ij}\) and \(\langle v_i \rangle + H_{il}\) respectively. Hence, \(r(x|W) \neq r(y|W)\).
• (e) If x belongs to \(H_{ij}\) and y belongs to \(H_{kl}\) for \(i \neq k\), then \(d(x, v_i) \neq d(x, v_k)\). Consequently, \(r(x|(B_{ij} \cup B_{kl} - \{v_i\}) \neq r(y|(B_{ij} \cup B_{kl} - \{v_i\}))\). \(r(x|W) \neq r(y|W)\) and \(W = \bigcup_{i=1}^n \bigcup_{i=1}^k (B_{i,i} - \{v_i\})\) is a resolving set of \(G \odot_k H\).

We now show that W is minimal. Suppose S is any set such \(S \subseteq V(G \odot_k H)\)and |S| < |W|. Then, S contains at most \(|B_{ij}| - 2\) elements of \(\langle v_i \rangle + H_{ij}\) for some index j. As a result, there are two distinct vertices of \(H_{ij}\) that have the same representation with respect to S. Therefore, W is a basis of \(G \odot_k H\) and \(\dim(G \odot_k H) = |W| = kn \left(\dim(K_1 + H) - 1\right).\)

• (II) Now we consider the second case, where there is no basis of \(K_1 + H\)containing a vertex of \(K_1\). Choose \(W = \bigcup_{i=1}^n \bigcup_{j=1}^k (B_{ij})\). Since \(\langle v_i \rangle + H_{ii} \cong\)\(K_1 + H, \forall i = 1,2, n; j = 1,2,..., k\), we have \(|W| = nk (dim (K_1 + H))\). Suppose x,y are any two distinct vertices of \(G \odot_k H\). Then there are five possibilities, namely:
  • (a) x and y belong to G.
  • (b) x and y belong to \(H_{ij} \cong H_i\).
  • (c) x belongs to G and y belongs to \(H_{ij} \cong H_i\).
  • (d) x belongs to \(H_{i,i}\) and y belongs to \(H_{i,l}\), where \(j \neq l\).
  • (e) x belongs to \(H_{ij}\) and y belongs to \(H_{kl}\) for \(i \neq k\).

By using the same technique as presented in the first case, it can be shown that \(W = \bigcup_{i=1}^n \bigcup_{j=1}^k (B_{ij})\) is a resolving set of \(G \odot_k H\). Now, we show that W is minimal. Let S be any set such that \(S \subseteq V(G \odot_k H)\) and |S| < |W|. Then, S contains at most \(|B_{ij}| - 1\) elements of \(\langle v_i \rangle + H_{ij}\) for some index j. Since \(B_{ij}\) is a basis of \(\langle v_i \rangle + H_{ij}\) and \(v_i \notin B_{ij}\), then there are two distinct vertices of \(H_{ij}\) that have the same representation with respect to S. Thus S is not a resolving set. Therefore, W is a basis of \(G \odot_k H\) and \(\dim(G \odot_k H) = |W| = nk (\dim(K_1 + H))\).

A more general result on the metric dimension of the generalized corona product of graphs is presented in the following theorem.

Theorem 8. Let G be a connected labelled graph of order n and \(\mathcal{H}\) be a sequence of n rooted graphs. If \(K_1 + H_i\) has a basis \(B_i\) such that there is no vertex x in \(H_i\) with \(r(x|B_i) = (2, 2, ..., 2)\) for every i. Then:

\(\dim(G \odot_k \mathcal{H}) = k \sum_{i=1}^n (\dim(K_1 + H_i) - \alpha_i)\), where:

\[\alpha_i = \begin{cases} 1, & \text{if there is a basis of } K_1 + H_i \text{ containing vertex of } K_1 \\ 0, & \text{otherwise} \end{cases}\]

Proof. Let G be a connected labelled graph of order n and \(\mathcal{H}\) be a sequence of n rooted graphs, namely \(H_1\), \(H_2\), \(H_3\), ..., \(H_n\) and k copies of \(\mathcal{H}\) are \(H_{11}\), \(H_{12}\), \(H_{13}\), ..., \(H_{1k}\), \(H_{21}\), \(H_{22}\), \(H_{23}\), ..., \(H_{2k}\), ..., \(H_{n1}\), \(H_{n2}\), \(H_{n3}\), ..., \(H_{nk}\). Let B be a basis of H and \(H_{ij}\) a basis of \(\{v_i\} + H_{ij}\), i = 1, 2, ..., n; j = 1, 2, ..., k. Since \(H_{ij} \cong H_i\), i = 1, 2, ..., n; j = 1, 2, ..., k, we have \(\{v_i\} + H_{ij} \cong \{v_i\} + H_i\) and \(H_{ij} \cong H_i\). Choose \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_i\) and \(H_{ij} \cong H_\)

\[\alpha_i = \begin{cases} 1, & \text{if there is a basis of } K_1 + H_i \text{ containing vertex of } K_1 \\ 0, & \text{otherwise} \end{cases}\]

Suppose x,y are any two distinct vertices in \(G \odot_k H\). Then there are five possibilities, namely:

• (a) x and y belong to G.
• (b) x and y belong to \(H_{i,i} \cong H_i\).
• (c) x belongs to G and y belongs to \(H_{ij} \cong H_i\).
• (d) x belongs to \(H_{ij}\) and y belongs to \(H_{il}\), where \(j \neq l\).
• (e) x belongs to \(H_{ij}\) and y belongs to \(H_{kl}\) for \(i \neq k\).

By using the same technique as presented in the proof of Theorem 7, it can be shown that \(W = \bigcup_{i=1}^{n} \bigcup_{j=1}^{k} (B_{ij} - \{v_i\})\) is a resolving set of \(G \odot_k \mathcal{H}\). Now, we

show that W is minimal. Suppose S is any set such that \(S \subseteq V(G \odot_k \mathcal{H})\) and |S| < |W|. Then, S contains at most \(|B_{ij} - \{v_i\}| - 1\) elements of \(\langle v_i \rangle + H_{ij}\) for some index j. Consequently, there are two distinct vertices of \(H_{ij}\) that have the same representation with respect to S. Thus, S is not a resolving set. Therefore, W is a basis of \(G \odot_k \mathcal{H}\) and \(\dim(G \odot_k \mathcal{H}) = |W| = k \sum_{i=1}^n (\dim(K_1 + H_i) - K_i)\)\(\alpha_i\)), where:

\[\alpha_i = \begin{cases} 1, & \text{if there is a basis of } K_1 + H_i \text{ containing vertex of } K_1 \\ 0, & \text{otherwise} \end{cases}.\]

For junior researchers it is advisable to read the paper of Susilowati, et al. in [7] to facilitate understanding of the proof.

5 Commutative Characterization of Comb and Corona Products of Graphs with Respect to Metric Dimension

In this section, we present a commutative characterization with respect to the metric dimension of the comb product, the corona product, the generalized comb product and the generalized corona product of two graphs. The commutative characterization of the comb product of graphs are presented in the following theorems.

The first one shows the conditions when the grafting vertex is an element of the basis and the second one shows the conditions when the grafting vertex is not an element of the basis.

Corollary 9. Let G and H be connected non path graphs of order at least two. Let the grafting vertex of GoH be an element of basis of H and the grafting vertex of HoG an element of the basis of G. Then:

\[|V(G)|\dim(H) - 1\rangle = |V(H)|(\dim(G) - 1) \Leftrightarrow (GoH) \cong \dim(HoG)\]

Proof. \((\Rightarrow)\) Suppose \(|V(G)|\dim(H)-1)=|V(H)|(\dim(G)-1)\). By using Theorem 1, we get \(\dim(G \circ H) = |V(G)|(\dim(H) - 1)\) and \(\dim(H \circ G) =\)\(|V(H)|(\dim(G) - 1)\). Hence, we find \(\dim(G \circ H) = \dim(H \circ G)\) or \((G \circ H) \cong\)\(\dim(HoG)\).

\((\Leftarrow)\) Suppose \((G \circ H) \cong \dim(H \circ G)\) or \((G \circ H) = \dim(H \circ G)\). By applying Theorem 1 again, we find \(\dim(G\circ H) = |V(G)|(\dim(H) - 1)\) and \(\dim(H\circ G) =\)\(|V(H)|(\dim(G)-1)\). This yields:

\[|V(G)|(\dim(H)-1)=|V(H)|(\dim(G)-1).\]

Corollary 10. Let G and H be connected non path graphs of order at least two. Let the grafting vertex of GoH not be an element of basis of H and the grafting vertex of H o G not be an element of the basis of G. Then:

\[|V(G)|(\dim(H)) = |V(H)|(\dim(G)) \Leftrightarrow (GoH) \cong \dim(HoG)\]

Proof. This theorem immediately follows from applying Theorem 1 and using the same steps as in Theorem 9.

We now show the commutative characterization of the generalized comb product of graphs with respect to the metric dimension with the following theorems.

Corollary 11. Let G and H be connected non path graphs of order at least two. If the grafting vertex of \(Go_kH\) is an element of the basis of H and the grafting vertex of H \(o_kG\) is an element of the basis of G, then:

\[(G \circ_k H) \cong \dim(H \circ_k G) \Leftrightarrow |V(G)| (\dim(H) - 1) = |V(H)| (\dim(G) - 1).\]

Proof. (\(\Rightarrow\)) Suppose \((Go_kH) \cong_{dim} (Ho_kG)\). We get that \(\dim(Go_kH) = \dim(Ho_kG)\). By using Theorem 4, we obtain \(k|V(G)|(\dim(H)-1) = k|V(H)|(\dim(G)-1)\). Hence, we get:

\[|V(G)|(\dim(H) - 1) = |V(H)|(\dim(G) - 1).\]

(\(\Leftarrow\)) Suppose \(|V(G)| (\dim(H) - 1) = |V(H)| (\dim(G) - 1)\). Then, \(k|V(G)| (\dim(H) - 1) = k|V(H)| (\dim(G) - 1)\). By using Theorem 4 again, we get \(\dim(G \circ_k H) = \dim(H \circ_k G)\), so \((G \circ_k H) \cong \dim(H \circ_k G)\).

Corollary 12. Let G and H be connected non path graphs of order at least two. If the grafting vertex of \(Go_kH\) is not an element of the basis of H and the grafting vertex of \(Ho_kG\) is not an element of the basis of G, then:

\[(Go_k H) \cong \dim(Ho_k G) \iff |V(G)| (\dim(H)) = |V(H)| (\dim(G)).\]

Proof. This theorem immediately follows from applying Theorem 4 and using the same steps as in Theorem 11.

The two theorems below show the commutative characterization of the corona product of graphs with respect to the metric dimension when both graphs either contain a dominant vertex or do not contain a dominant vertex.

Corollary 13. Let G and H be connected graphs of order \(n \ge 2\) containing a dominant vertex. Then, \(|G| \dim(H) = |H| \dim(G) \Leftrightarrow G \odot H \cong \dim(H \odot G)\).

Proof. (\(\Rightarrow\)) Suppose \(|G| \dim(H) = |H| \dim(G)\). By using Theorem 2, we get \(\dim(G \odot H) = |G| \dim(H)\) and \(\dim(H \odot G) = |H| \dim(G)\). Hence, we find \(\dim(G \odot H) = |H| \dim(G) = \dim(H \odot G)\). So \((G \odot H) \cong \dim(H \odot G)\).

(⇐) Suppose \((G \odot H) \cong \dim(H \odot G)\) or \((G \odot H) = \dim(H \odot G)\). By applying Theorem 2 again, we find \(\dim(G \odot H) = |G|\dim(H)\) and \(\dim(H \odot H)\)\(G(G) = |H| \dim(G)\). This yields \(|G| \dim(H) = |H| \dim(G)\).

Corollary 14. Let G and H be connected graphs of order \(n \ge 2\) containing no dominant vertex. Then \(|G|\dim(K_1 + H) = |H|\dim(K_1 + G) \Leftrightarrow (G \odot H) \cong\)\(\dim(H \odot G)\).

Proof. This theorem immediately follows from applying Theorem 2 and using the same steps as in Theorem 13.

We now show the commutative characterization of the generalized corona product of graphs with respect to the metric dimension with the following theorems.

Corollary 15. Let G and H be connected graphs of order at least two. Let the vertex of \(K_1\) be an element of the basis \(K_1 + H\) and the vertex of \(K_1\) an element of the basis \(K_1 + G\). If \(K_1 + H\) has a basis B so that there is no vertex x in H with r(x|B) = (2, 2, ..., 2) and \(K_1 + G_i\) has a basis C so that there is no vertex \(x \text{ in } G_i \text{ with } r(x|C) = (2, 2, ..., 2), \text{ then:}\)

\[(G \odot_k H) \cong_{dim} (H \odot_k G) \Leftrightarrow |V(G)| (\dim(K_1 + H) - 1) = |V(H)| (\dim(K_1 + G) - 1).\]

Proof. \((\Rightarrow)\) Let G and H be connected graphs of order at least two. Suppose the vertex of \(K_1\) is an element of basis \(K_1 + H\) and the vertex of \(K_1\) is an element of basis \(K_1 + G\), and \((G \odot_k H) \cong \dim(H \odot_k G)\). By using Theorem 6, we obtain: \(k|V(G)|(\dim(K_1 + H) - 1) = k|V(H)|(\dim(K_1 + G) - 1)\). Hence, we find \(|V(G)| (\dim(K_1 + H) - 1) = |V(H)| (\dim(K_1 + G) - 1).\)

\((\Leftarrow)\) Suppose \(|V(G)|(\dim(K_1 + H) - 1) = |V(H)|(\dim(K_1 + G) - 1)\). Then, \(k|V(G)|(\dim(K_1 + H) - 1) = k|V(H)|(\dim(K_1 + G) - 1)\). By using Theorem 6 again, we find \(\dim(G \odot_k H) = \dim(H \odot_k G)\), so \((G \odot_k H) \cong\)\(dim(H \odot_k G)\).

Corollary 16. Let G and H be connected graphs of order at least two. Suppose the vertex of \(K_I\) is not an element of basis \(K_1 + H\) and the vertex of \(K_I\) is not an element of basis \(K_1 + G\). If \(K_1 + H\) has a basis B such that there is no vertex x in H r(x|B) = (2, 2, ..., 2) and \(K_1 + G_i\) has a basis C such that there is no vertex x in \(G_i\) with r(x|C) = (2, 2, ..., 2), then:

\[(G \odot_k H) \cong \dim(H \odot_k G) \Leftrightarrow |V(G)| (\dim(K_1 + H)) = |V(H)| (\dim(K_1 + G)).\]

Proof. This theorem immediately follows from applying Theorem 6 and using the same steps as in Theorem 15.

6 Conclusion

In this paper, the metric dimensions of the k-comb and the k-corona products of graphs were discussed. Suppose we state the k-comb and k-corona in this paper as (k, k, k,… k)-comb and (k, k, k,… k)-corona respectively. We conclude this paper with open problems on the metric dimension of (k1, k2, k3,… kn)-comb and (k1, k2, k3,… kn)-corona of graph G of order n and n sequence of graphs .

Acknowledgements

This research was supported by DIKTI Indonesia through the Penelitian Unggulan Perguruan Tinggi, DRPM RISTEKDIKTI 2016 research project.