D. Fitriani, S.W. Saputro

Combinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences Institut Teknologi Bandung, Indonesia.

dinny.fitriani@gmail.com, suhadi@itb.ac.id

For any two adjacent vertices u and v in graph G, a set of vertices W locally resolves a graph G if the distance of u and v to some elements of W are distinct. The local metric dimension of G is the minimum cardinality of local resolving sets of G. For n ∈ N and i ∈ {1, 2, . . . , n}, let Hⁱ be a simple connected graph containing a connected subgraph J. Let H = {H1, H2, . . . , Hn} be a finite collection of simple connected graphs. The subgraph-amalgamation of H = {H1, H2, . . . , Hn}, denoted by Subgraph − Amal{H; J}, is a graph obtained by identifying all elements of H in J. The subgraph J is called as a terminal subgraph of H. In this paper, we determine general bounds of the local metric dimension of subgraph-amalgamation graphs for any connected terminal subgraphs. We also determine the local metric dimension of Subgraph − Amal{H; J} for J is either K¹ or P2.

Keywords: local basis, local metric dimension, local resolving set, subgraph-amalgamation

Mathematics Subject Classification : 05C12, 05C76

DOI: 10.5614/ejgta.2024.12.1.11

1. Introduction

Throughout this paper, all graphs are finite, simple and connected. Let G be a graph. We denote the vertex set and the edge set of G by V (G) and E(G), respectively. The distance between two vertices u and v of G, denoted by dG(u, v), is the length of a shortest path from u to v in G. Let

Received: 17 August 2022, Revised: 26 November 2023, Accepted: 5 April 2024.

W = {w1, w2, ..., wk} be a subset of V (G). The representation of v with respect to W is defined as the k-tuple r(v | W) = (dG(v, w1), dG(v, w2), . . . , dG(v, wk)). The set W is called as a resolving set of G if every two distinct vertices u and v of G has different representations. A resolving set with minimum cardinality is called a basis of G and its cardinality is called as the metric dimension of G, denoted by dim(G).

The metric dimension was first studied by Slater [34] and independently by Harary and Melter [15]. Since then, this topic has been widely investigated. All graphs with certain metric dimension have been studied in [9, 16, 18]. The metric dimension of certain classes of graph is also determined, including trees [15, 19, 9], cycles [9], unicyclic graphs [24], wheels [6, 7, 32], fans [7], Cayley graphs [12], Jahangir graphs [36], honeycomb networks [22], regular graphs [29], Sierpinski graphs [21], amalgamation of graphs [33], and fullerene graphs [2]. This topic also ´ has been arised in many applications, such as network discovery and verification [5], robotic navigation [10, 19], and mastermind [14]. Some other results on metric dimension can be seen in [8, 17, 19, 27, 30, 31, 35, 37]

In this paper, we consider a variance of metric dimension, namely local metric dimension. In this version, two different vertices may have the same representation with respect to an ordered subset W of V (G). In case r(u | W) 6= r(v | W) for every adjacent vertices u and v in G, then the set W is called a local resolving set of G. A local resolving set with minimum cardinality is called a local basis of G and its cardinality is called the local metric dimension of G, denoted by lmd(G). Since a resolving set of G also a local resolving set of G, then trivially we have 1 ≤ lmd(G) ≤ dim(G).

The local metric dimension problem was introduced by Okamoto et al. [23]. They proved that bipartite graphs are the only graphs having local metric dimension one. Moreover, they also showed that lmd(G) = n − 1 if and only if G is a complete graph of order n. Furthermore, they also characterized all graphs of order n whose local metric dimension n − 2. The local metric dimension of some certain particular graphs also has been determined, including graphs with small clique number [1], torus networks [11], regular graphs [28], block graphs [26], bouquet graphs [26], and split graphs [13].

Determining a relation, in terms of local metric dimension, between the origin graph and the resulting graph under a graph operation is also interesting to be considered. The local metric dimension of Cartesian product graphs has been investigated in [23]. Meanwhile, Rodr´ıguez-Velazquez ´ et al. studied the parameter for corona product graphs [25] and rooted product graphs [26]. The lower and upper bounds on the local metric dimension of the generalized hierarchical product are proved in [20]. Barragan-Ram ´ ´ırez et al. determined the local metric dimension of lexicographic product graphs [3] and strong product graphs [4].

Now, for n ∈ N and i ∈ {1, 2, . . . , n}, let us consider a simple connected graph Hⁱ containing a connected subgraph J. Let H = {H1, H2, . . . , Hn} be a finite collection of simple connected graphs. The subgraph-amalgamation of H = {H1, H2, . . . , Hn}, denoted by Subgraph − Amal{H; J}, is a graph obtained by identifying all elements of H in J. The subgraph J is called as a terminal subgraph of H. In this paper, we determine general bounds of the local metric dimension of subgraph-amalgamation graphs for any connected terminal subgraphs. We also determine the local metric dimension of Subgraph − Amal{H; J} for J is either K¹ or P2.

2. Subgraph Amalgamation

For \(n \in \mathbb{N}\) and \(i \in \{1, 2, ..., n\}\), let \(H_i\) be a simple connected graph of order \(k_i \geq 2\) containing a connected subgraph J of order p where \(1 \leq p < k_i\). Let \(V(H_i) = \{h_1, h_2, ..., h_p, h_{p+1}, ..., h_{k_i}\}\) where \(V(J) = \{h_1, h_2, ..., h_p\}\).

Now, let us consider \(\mathcal{H} = \{H_1, H_2, \dots, H_n\}\). In this section, we denote \(H \cong Subgraph - Amal\{\mathcal{H}; J\}\). We define \(V(H) = V(J) \cup \{h_{(i,j)} | 1 \le i \le n, p+1 \le j \le k_i\}\) and \(H_i^* = V(J) \cup \{h_{(i,j)} | p+1 \le j \le k_i\}\).

Figure 1. Subgraph amalgamation of \(H_1, H_2, \dots, H_n\)

In Lemma 2.1 below, we prove that every graph \(G \in \mathcal{H}\) contibutes at least lmd(G) - p vertices in a local basis of H. Meanwhile in Lemma 2.2, we provide a local resolving set of subgraph-amalgamation H, which is union of local basis of every graph in \(\mathcal{H}\).

Lemma 2.1. Let W be a local basis of \(H \cong Subgraph - Amal\{\mathcal{H}; J\}\). Then every graph \(G \in \mathcal{H}\) contibutes at least lmd(G) - p vertices in W.

Proof. Suppose that there exists \(i \in \{1, 2, \dots, n\}\) such that \(H_i\) contributes at most \(lmd(H_i) - p - 1\) vertices in W. Let \(W_i = W \cap V(H_i)\) and \(S_i = \{h_t \mid h(i,t) \in W_i\}\). Now, we define \(A_i = S_i \cup V(J)\). Note that \(|A_i| < lmd(H_i)\). Since all vertices of J are in \(A_i\), so there exist two adjacent vertices \(h_k\) and \(h_l\) in \(V(H_i) \setminus V(J)\) satisfying \(r(h_k \mid A) = r(h_l \mid A)\), which implies \(r(h_{(i,k)} \mid W_i) = r(h_{(i,l)} \mid W_i)\). Since every vertex \(z \in V(H) \setminus V(H_i)\) and \(u \in V(H_i) \setminus V(J)\) satisfies \(d_H(z,u) = d_H(z,v) + d_H(v,u)\) for some \(v \in V(J)\), it follows that \(r(h_{(i,k)} \mid W) = r(h_{(i,l)} \mid W)\), a contradiction.

Lemma 2.2. Let \(B_i\) be a local basis of \(H_i\). Then \(W = \bigcup_{i=1}^n B_i\) be a local resolving set of \(H \cong Subgraph - Amal\{\mathcal{H}; J\}\).

Proof. Let us consider an edge \(xy \in E(H)\). Then there exists \(i \in \{1, 2, ..., n\}\) such that \(x, y \in V(H_i)\). Since every two adjacent vertices in \(H_i\) are locally resolved by some vertices of \(B_i\), we obtain that \(W = \bigcup_{i=1}^n B_i\) is a local resolving set of H.

By considering Lemmas 2.1 and 2.2, we obtain the lower and upper bounds for the local metric dimension of subgraph-amalgamation graphs, which can be seen in theorem below.

Theorem 2.1. For \(n \ge 2\) and \(i \in \{1, 2, ..., n\}\), let \(H_i\) be a simple connected graph containing a connected subgraph J and \(\mathcal{H} = \{H_1, H_2, ..., H_n\}\). Let |V(J)| = p. Then

\[\sum_{i=1}^{n} lmd(H_i) - pn \leq lmd(Subgraph - Amal\{\mathcal{H}; J\}) \leq \sum_{i=1}^{n} lmd(H_i).\]

In the theorem below, we provide a property of subgraph-amalgamation graph H such that its local metric dimension satisfies the upper bound in Theorem 2.1.

Theorem 2.2. For \(n \geq 2\) and \(i \in \{1, 2, ..., n\}\), let \(H_i\) be a simple connected graph containing a connected subgraph J and \(\mathcal{H} = \{H_1, H_2, ..., H_n\}\). If every local basis of \(H_i\) \((1 \leq i \leq n)\) does not contain all vertices of J and every vertex in J is adjacent to every vertex in \(V(H_i) \setminus V(J)\), then \(Imd(Subgraph - Amal\{\mathcal{H}; J\}) = \sum_{i=1}^{n} Imd(H_i)\).

Proof. By Theorem 2.1, we only need to show that \(lmd(H) \ge \sum_{i=1}^{n} lmd(H_i)\).

Suppose that \(lmd(H) \leq (\sum_{i=1}^n lmd(H_i)) - 1\) and W be a local basis of H. Let \(B_i\) be a local basis of \(H_i\). Note that \(B_i\) does not contain all vertices of J. Then there exists \(i \in \{1, 2, \ldots, n\}\) such that \(h_{(i,l)} \notin W\) where \(h_l \in B_i\). Let \(B_i' = B_i \setminus \{h_l\}\). Since \(|B_i'| < lmd(H_i)\), there exist two adjacent vertices \(h_s, h_t\) in \(H_i\) satisfying \(r(h_s \mid B_i') = r(h_t \mid B_i')\). Let \(B(i)' = \{h_{(i,k)} \mid h_k \in B_i'\}\). Thus, \(r(h_{(i,s)} \mid B(i)') = r(h_{(i,t)} \mid B(i)')\). Since \(d_H(h_{(i,s)}, h_j) = d_H(h_{(i,t)}, h_j)\) for each \(h_{(i,s)}, h_{(i,t)} \in V(H) \setminus V(J)\) and \(j \in \{1, 2, \ldots, p\}\), we obtain that \(r(h_{(i,s)}|W) = r(h_{(i,t)}|W)\), a contradiction. \(\square\)

In order to provide a property of subgraph-amalgamation graph H such that its local metric dimension satisfies the lower bound in Theorem 2.1, we need to prove Theorem 2.3 below. In this theorem, we give a property of subgraph-amalgamation graph whose local metric dimension is equal to \(\sum_{i=1}^n lmd(H_i) - cn\) where \(0 < c \le p\). If c = p, then we have a subgraph-amalgamation graph H where lmd(H) is equal to the lower bound in Theorem 2.1

Theorem 2.3. For \(n \geq 2\) and \(i \in \{1, 2, ..., n\}\), let \(H_i\) be a simple connected graph containing a connected subgraph J and \(\mathcal{H} = \{H_1, H_2, ..., H_n\}\). Let \(|V(J)| = p \geq 1\) and \(V(J) = \{h_1, h_2, ..., h_p\}\). Let C be a non-empty subset of V(J) where \(C = \{h_1, h_2, ..., h_c\}\). Let \(Imd(H_i) \geq 2c\) and every local basis \(B_i\) of \(H_i\) contains \(x \in V(J)\) if and only if \(x \in C\). If there exists a subset \(\{h_{p+1}, h_{p+2}, ..., h_{p+c}\}\) of \(B_i \setminus C\) such that \(d_{H_i}(h_j, h_{p+j}) < d_{H_i}(h_k, h_{p+j})\) for every distinct \(j, k \in \{1, 2, ..., c\}\), then \(Imd(Subgraph - Amal\{\mathcal{H}; J\}) = \sum_{i=1}^n Imd(H_i) - cn\).

Proof. Suppose that W is a local basis of H satisfying \(|W| = lmd(H) \le (\sum_{i=1}^n lmd(H_i) - cn) - 1\). Then there exists \(i \in \{1, 2, \dots, n\}\) such that \(H_i\) contributes at most \(lmd(H_i) - c - 1\) vertices in W. Let \(S_i = W \cap V(H_i)\) and \(W_i = \{h_j \in V(H_i) \mid h_{(i,j)} \in S_i\}\), then \(|W_i| \le lmd(H_i) - c - 1\). Let \(A \subseteq C\) where every element of A, say \(h_b\), locally resolves some two adjacent vertices in \(H_i^*\) and there exists \(v \in W \setminus H_i^*\) which satisfies \(d_H(v, h_b) = min\{d_H(v, w) \mid w \in C\}\). Since every local basis \(B_i\) of \(H_i\) does not contain all vertices of \(V(J) \setminus C\) and \(|W_i \cup A| < |B_i|\), there exist two adjacent vertices \(h_k, h_l\) in \(H_i\) which are not locally resolved by vertices in \(W_i \cup A\), which implies

\(h_{(i,k)}, h_{(i,l)}\) are not locally resolved by vertices in \(S_i \cup A\). It follows that \(h_{(i,k)}, h_{(i,l)}\) are not locally resolved by W, a contradiction.

For \(i \in \{1, 2, ..., n\}\), let \(T_i = B_i \setminus C\). We define \(U_i = \{h_{(i,l)} \mid h_l \in T_i\}\) and \(W = \bigcup_{i=1}^n U_i\). We will show that W is a local resolving set of H.

We consider any two adjacent vertices \(h_{(i,s)}, h_{(i,t)} \in V(H) \setminus W\) in two following cases.

• There exist \(h_s\), \(h_t\) in \(H_i\) which are locally resolved by \(W_i\). Let \(h_l \in T_i\) locally resolves \(h_s\) and \(h_t\). Then it is clear that \(h_{(i,s)}\), \(h_{(i,t)}\) in H will be locally resolved by \(h_{(i,l)} \in W\).
• Every two adjacent vertices \(h_s, h_t\) in \(H_i\) are not locally resolved by \(W_i\). Then there exists \(h_j \in C\) such that \(d_{H_i}(h_s, h_j) \neq d_{H_i}(h_t, h_j)\). Therefore, we have \(d_H(h_{(i,s)}, h_j) \neq d_H(h_{(i,t)}, h_j)\). We consider \(h_{(m,p+j)} \in W\) where \(m \in \{1, 2, \dots, n\} \setminus \{i\}\) and \(d_{H_i}(h_j, h_{(p+j)}) < d_{H_i}(h_k, h_{(p+j)})\) for every distinct \(j, k \in \{1, 2, \dots, p\}\). We obtain

\[\begin{split} d_H(h_{(i,s)},h_{(m,p+j)}) &= d_H(h_{(i,s)},h_j) + d_H(h_j,h_{(m,p+j)}) \\ &= d_H(h_{(i,s)},h_j) + d_{H_i}(h_j,h_{p+j}) \\ &\neq d_H(h_{(i,t)},h_j) + d_{H_i}(h_j,h_{p+j}) \\ &= d_H(h_{(i,t)},h_j) + d_H(h_{(j)},h_{(m,p+j)}) \\ &= d_H(h_{(i,t)},h_{(m,p+j)}). \end{split}\]

Then \(h_{(i,s)}, h_{(i,t)}\) in H are locally resolved by \(h_{(m,p+j)} \in W\).

Therefore, W is a local resolving set of H.

Note that, in Theorem 2.3 above, we consider a graph \(Subgraph - Amal\{\mathcal{H}; J\}\) where every local basis of \(H_i \in \mathcal{H}\) \((1 \le i \le n)\) contains the same exactly c vertices of J. In theorem below, we can prove that the upper bound of the local metric dimension of such subgraph-amalgamation graph is less than the upper bound in Theorem 2.1.

Theorem 2.4. For \(n \ge 2\) and \(i \in \{1, 2, ..., n\}\), let \(H_i\) be a simple connected graph containing a connected subgraph J and \(\mathcal{H} = \{H_1, H_2, ..., H_n\}\). Let \(|V(J)| = p \ge 1\) and C be a non-empty subset of V(J) where |C| = c. Let every local basis \(B_i\) of \(H_i\) contains \(x \in V(J)\) if and only if \(x \in C\). Then

\[lmd(Subgraph - Amal\{\mathcal{H}; J\}) \le \sum_{i=1}^{n} lmd(H_i) - cn + c.\]

Proof. Let us consider any edges \(xy \in E(H)\). Then there exists \(i \in \{1, 2, ..., n\}\) such that \(x, y \in V(H_i)\). For \(i \in \{1, 2, ..., n\}\), let \(B_i\) be a local basis of \(H_i\). Since every two adjacent vertices in \(H_i\) are locally resolved by some vertices in \(B_i\), we obtain that \(W = \bigcup_{i=1}^n B_i\) is a local resolving set of H. Since \(|B_i \cap B_j| = c\) for distinct \(i, j \in \{1, 2, ..., n\}\), we have \(|W| = \sum_{i=1}^n |B_i| - (n-1)c\). Therefore, we obtain

\[lmd(H) \le \sum_{i=1}^{n} lmd(H_i) - cn + c.\]

Next, we will show that the upper bound in Theorem 2.4 is sharp. In order to do so, first, we need to determine the local metric dimension of graph G1, which can be seen in lemma below. The graph G¹ and its complement are shown in Figure 2.

Figure 2. Graph G¹ (left) and its complement (right)

Lemma 2.3. Let G¹ be a connected graph as stated in Figure 2. Then lmd(G1) = 3. Moreover, the set {f1, f2, f3} is the only local basis of G1.

Proof. Let D = {dⁱ | i ∈ {1, 2, 3}}, E = {eⁱ | i ∈ {1, 2, 3}}, F = {fⁱ | i ∈ {1, 2, 3}}, and G = {gⁱ | i ∈ {1, 2, 3}}. Since G¹ contains an odd cycle, we have lmd(G1) > 1. We will show that there is no local resolving set of G¹ whose cardinality is 2. Suppose that W be a local resolving set of G¹ with |W| = 2. We distinguish four cases.

Case 1. W ⊂ D ∪ F

Since |W| = 2, there exists i ∈ {1, 2, 3} such that fⁱ ∈/ W. So, we obtain that r(eⁱ | W) = (1, 1) = r(gⁱ | W).

Case 2. W ⊂ D ∪ E ∪ G

Then D \ W 6= ∅ and E \ W 6= ∅. Let dⁱ , e^j ∈/ W. Note that dⁱ and e^j are adjacent. So, we obtain that r(dⁱ | W) = (1, 1) = r(e^j | W).

Case 3. W = {eⁱ , fj} where i, j ∈ {1, 2, 3}.

Then two adjacent vertices fk, g^l satisfy r(f^k | W) = (1, 1) = r(g^l | W) with k, l ∈ {1, 2, 3} and k 6= i, l 6= j.

Case 4. W = {fⁱ , gj} where i, j ∈ {1, 2, 3}.

Then two adjacent vertices ek, e^l satisfy r(e^k | W) = (1, 1) = r(e^l | W) with k, l ∈ {1, 2, 3} \ {i}

and k 6= l.

By all cases above, we conclude that W is not local resolving set of G1. Since there is no local resolving set of G¹ with 2 elements, we obtain that lmd(G1) ≥ 3.

Now, we will construct a local resolving set of G¹ with 3 vertices. Define B = {f1, f2, f3}. The representation of all vertices in G¹ with respect to B are as follows.

\[r(d_1|B) = (1,2,2)\] \(r(e_2|B) = (1,2,1)\) \(r(f_3|B) = (1,1,0)\)
\(r(d_2|B) = (2,1,2)\) \(r(e_3|B) = (1,1,2)\) \(r(g_1|B) = (1,1,1)\)
\(r(d_3|B) = (2,2,1)\) \(r(f_1|B) = (0,1,1)\) \(r(g_2|B) = (1,1,1)\)
\(r(e_1|B) = (2,1,1)\) \(r(f_2|B) = (1,0,1)\) \(r(g_3|B) = (1,1,1)\)

Since there are no two adjacent vertices of G¹ having the same representation, we obtain that B is a local resolving set of G1, which implies lmd(G1) ≤ 3.

Next, we will show that there is no local resolving set of G¹ with 3 vertices, except {f1, f2, f3}. Let W⁰ ⊂ V (G1) with |W⁰ | = 3 and W⁰ contains q vertices in F with 0 ≤ q ≤ 2. We distinguish three cases.

Case 1. q = 0

• W⁰ ∩ G = ∅ If W⁰ = E, then two adjacent vertices d ∈ D and g ∈ G satisfy r(d | W⁰ ) = (1, 1, 1) = r(g | W⁰ ). Otherwise, let eⁱ ∈/ W (i ∈ {1, 2, 3}). Then we obtain r(eⁱ | W⁰ ) = (1, 1, 1) = r(gⁱ | W⁰ ).
• W⁰ ∩ G 6= ∅ Then there exist d ∈ D and e ∈ E which are not element of W⁰ . Then we obtain r(d | W⁰ ) = (1, 1, 1) = r(e | W⁰ ).

Case 2. q = 1

• W⁰ ∩ G = ∅ If W⁰ ∩ D = ∅, then two adjacent vertices d ∈ D and g ∈ G satisfy r(d | W⁰ ) = (1, 1, 1) = r(g | W⁰ ). Otherwise, let eⁱ ∈/ W (i ∈ {1, 2, 3}). Then we obtain r(eⁱ | W⁰ ) = (1, 1, 1) = r(gⁱ | W⁰ ).
• W⁰ ∩ G 6= ∅ If W⁰ ∩ E = ∅, then there exist two distinct vertices of E which are adjacent to W⁰ . Otherwise, all three vertices of D are adjacent to W⁰ .

Case 3. q = 2

Let two distinct vertices f^j , f^k ∈ W⁰ where j, k ∈ {1, 2, 3}.

• W⁰ ∩ D 6= ∅ Then for l ∈ {1, 2, 3} \ {j, k}, we have e^l is adjacent to W⁰ . So, for g ∈ G, we obtain r(e^l | W⁰ ) = (1, 1, 1) = r(g | W⁰ ).

• \(W' \cap G \neq \emptyset\)Then two adjacent vertices \(d_i, e_k\) satisfy \(r(d_i \mid W') = r(e_k \mid W')\).
• \(W' \cap E \neq \emptyset\)Let \(e_i \in W'\). If i = j, then two adjacent vertices \(d_j, e_k\) satisfy \(r(d_j \mid W') = r(e_k \mid W')\). Otherwise, two adjacent vertices \(d_k, e_j\) satisfy \(r(d_k \mid W') = r(e_j \mid W')\).

By all cases above, W' is not local resolving set of \(G_1\).

Now, we are ready to give an existence of \(\mathcal{H} = \{H_1, H_2, \dots, H_n\}\) and a terminal subgraph J of \(H_i\), such that the local metric dimension of \(Subgraph - Amal\{\mathcal{H}; J\}\) is equal to the upper bound of Theorem 2.4.

Theorem 2.5. For \(n \ge 2\) and \(i \in \{1, 2, ..., n\}\), let \(H_i \cong G_1\), J be a terminal subgraph of \(H_i\) with \(V(J) = \{f_1, f_2, e_3\}\), and \(\mathcal{H} = \{H_1, H_2, ..., H_n\}\). Then \(lmd(Subgraph - Amal\{\mathcal{H}; J\}) = n + 2\).

Proof. In this case, \(C = \{f_1, f_2\}\) and c = |C| = 2. By Theorem 2.4, \(lmd(H) \le \sum_{i=1}^{n} lmd(H_i) - cn + c = n + 2\). Now, we will prove that \(lmd(H) \ge \sum_{i=1}^{n} lmd(H_i) - cn + c = n + 2\).

Let \(x_{(i,j)} \in V(H) \setminus V(J)\) whenever \(x_j \in V(H_i) \setminus V(J)\) and W be a local resolving set of H. We consider two conditions below.

• 1. Two adjacent vertices \(d_1\) and \(e_2\) are not locally resolved by J. It follows that \(d_{(i,1)}\) and \(e_{(i,2)}\) in H are not locally resolved by \(V(H) \setminus H_i^{\star}\). Since \(f_3\) is an element of local basis of \(G_1\) and \(f_3\) locally resolves \(d_1\) and \(e_2\), we obtain that \(f_{(i,3)}\) locally resolves \(d_{(i,1)}\) and \(e_{(i,2)}\). Thus, \(f_{(i,3)} \in W\) for \(1 \le i \le n\).
• 2. For \(j \in \{1,2\}\), two adjacent vertices \(e_j\) and \(g_j\) are not locally resolved by \(J \setminus \{f_j\}\). According to Lemma 2.3, \(f_j\) is an element of a local basis of \(G_1\). Note that if \(f_j \notin W\), then \(e_{(i,j)}\) and \(g_{(i,j)}\) are not locally resolved by \(V(H) \setminus H_i^\star\) since \(d_H(v,e_{(i,j)}) < d_H(v,f_j) + d_H(f_j,e_{(i,j)})\) and \(d_H(v,g_{(i,j)}) = d_H(v,f_j) + d_H(f_j,g_{(i,j)})\) with \(v \in V(H) \setminus H_i^\star\). So, \(f_j\) must be in W for \(j \in \{1,2\}\).

By two conditions above, we obtain that \(lmd(H) \ge n + 2\).

In the next theorem, we will provide an existence of \(\mathcal{H} = \{H_1, H_2, \dots, H_n\}\) and a terminal subgraph J of \(H_i\), such that the local metric dimension of \(Subgraph - Amal\{\mathcal{H}, J\}\) is not equal to both upper bound of Theorem 2.4 and lower bound of Theorem 2.1. In order to do so, first, we need to determine the local metric dimension of graph \(G_2\), which can be seen in Lemma 2.4 below. The lemma is proved by using the similar argument of Lemma 2.3. Meanwhile, the graph \(G_2\) and its complement are shown in Figure 2. Note that, the graph \(G_2\) can be obtained from \(G_1\) by adding an edge \(f_1f_3\).

Lemma 2.4. Let \(G_2\) be a connected graph as stated in Figure 3. Then \(lmd(G_2) = 3\). Moreover, the set \(\{f_1, f_2, f_3\}\) is the only local basis of \(G_2\).

Theorem 2.6. For \(n \ge 2\) and \(i \in \{1, 2, ..., n\}\), let \(H_i \cong G_2\), J be a terminal subgraph of \(H_i\) with \(V(J) = \{f_1, f_2, e_3\}\), and \(\mathcal{H} = \{H_1, H_2, ..., H_n\}\). Then \(lmd(Subgraph - Amal\{\mathcal{H}; J\}) = n + 1\).

Figure 3. Graph \(G_2\) (left) and its complement (right)

Proof. In this case, \(C = \{f_1, f_2\}\) and c = |C| = 2. Note that, \(\sum_{i=1}^{n} lmd(H_i) - cn = n < n+1 < \sum_{i=1}^{n} lmd(H_i) - cn + c = n+2\).

Now, we will prove that \(lmd(H) \ge n + 1\). Let \(x_{(i,j)} \in V(H) \setminus V(J)\) whenever \(x_j \in V(H_i) \setminus V(J)\) and W be a local resolving set of H. We consider two conditions below.

• 1. Two adjacent vertices \(d_1\) and \(e_2\) are not locally resolved by J. It follows that \(d_{(i,1)}\) and \(e_{(i,2)}\) in H are not locally resolved by \(V(H) \setminus H_i^{\star}\). Since \(f_3\) is an element of local basis of \(G_2\) and \(f_3\) locally resolves \(d_1\) and \(e_2\), we obtain that \(f_{(i,3)}\) locally resolves \(d_{(i,1)}\) and \(e_{(i,2)}\). Thus, it must be \(f_{(i,3)} \in W\) for \(1 \le i \le n\).
• 2. Two adjacent vertices \(e_1\) and \(g_1\) are not locally resolved by \(J \setminus \{f_1\}\). According to Lemma 2, \(f_1\) is an element of a local basis of \(G_2\). Note that, if \(f_1 \not\in W\), then \(e_{(i,1)}\) and \(g_{(i,1)}\) are not locally resolved by \(V(H) \setminus H_i^{\star}\) since \(d_H(v, e_{(i,1)}) < d_H(v, f_1) + d_H(f_1, e_{(i,1)})\) and \(d_H(v, g_{(i,1)}) = d_H(v, f_1) + d_H(f_1, g_{(i,1)})\) with \(v \in V(H) \setminus H_i^{\star}\). So, \(f_1\) must be in W.

By two conditions above, we obtain that \(lmd(H) \ge n + 1\).

Now, we will construct a local resolving set of H with n+1 vertices. Define \(B = \{f_1\} \cup \{f_{(i,3)} \mid 1 \le i \le n\}\). The representation of all vertices in H with respect to B are as follows.

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

where k ∈ {3, 4, . . . , n} and dH(v(k,l) , f(i,3)) = d^G2 (vl , f3) for each v^l ∈ D ∪ E ∪ F ∪ G where i = k. Since there are no two adjacent vertices of H having the same representations, we obtain that B is a local resolving set of H, which implies lmd(H) ≤ n + 1.

3. Vertex Amalgamation

For n ∈ N and i ∈ {1, 2, . . . , n}, let Hⁱ be a simple connected graph of order kⁱ ≥ 2 containing a connected subgraph J of order p where 1 ≤ p < kⁱ . In this section, let H = {H1, H2, . . . , Hn} where J only consists of one vertex. The graph Subgraph−Amal{H, J} then is called as a vertex amalgamation graph.

Let V (Hi) = {h, h2, . . . , h^ki } where V (J) = {h}. In this section, we denote H ∼= Subgraph− Amal{H; J}. We define V (H) = {h} ∪ {h(i,j) |1 ≤ i ≤ n, 2 ≤ j ≤ ki}, H(i) = {h(i,j) |2 ≤ j ≤ ki}, and H? ⁱ = {h} ∪ H(i). We also define:

• S = {A ∈ H | A is not bipartite and there exists a local basis of A containing h}
• T = {A ∈ H | A is not bipartite and every local basis of A does not contain h}

From now on, let s = |S|, t = |T |, and H = {H1, H2, . . . , Hs, Hs+1, . . . , Hs+^t , Hs+t+1, . . . , Hn} where S = {H1, H2, . . . , Hs} and T = {Hs+1, Hs+2, . . . , Hs+t}.

Proposition 3.1. For s + t ≥ 1, there exist two adjacent vertices h(i,j) and h(i,k) satisfying dH(h(i,j) , h) = dH(h(i,k) , h) where i ∈ {1, 2, . . . , s + t} and j, k ∈ {2, 3, . . . , ki}.

Proof. Since s + t ≥ 1, for i ∈ {1, 2, . . . , s + t}, we have Hⁱ is not bipartite and contains an odd cycle C. We distinguish two cases.

Case 1. h ∈ V (C)

Then there exist two adjacent vertices h^j , h^k ∈ V (C)\ {h} satisfying d^Hi (h^j , h) = d^Hi (hk, h). We

obtain that dH(h(i,j) , h) = dH(h(i,k) , h).

Case 2. h /∈ V (C)

Let h^l ∈ V (C) such that d^Hi (h^l , h) = min{d^Hi (v, h)|v ∈ V (C)}. Then there exist two adjacent vertices h^j , h^k ∈ V (C) \ {hl} satisfying d^Hi (h^j , hl) = d^Hi (hk, hl) and

\[d_{H_i}(h_j, h) = d_{H_i}(h_j, h_l) + d_{H_i}(h_l, h)\]
= \(d_{H_i}(h_k, h_l) + d_{H_i}(h_l, h)\)
= \(d_{H_i}(h_k, h)\).

Therefore, we obtain that dH(h(i,j) , h) = dH(h(i,k) , h).

In the next two lemmas, we provide some properties of local basis of the vertex amalgamation graph H.

Lemma 3.1. Let W be a local basis of H. If s + t ≥ 1, then

• (i) W ∩ H(i) 6= ∅ for every i ∈ {1, 2, . . . , s + t}; and
• (ii) W ∩ H(j) = ∅ for every j ∈ {s + t + 1, s + t + 2, . . . , n}.

Proof. We distinguish two cases of proof.

(i) W ∩ H(i) 6= ∅ for every i ∈ {1, 2, . . . , s + t} Suppose that W ∩ H(i) = ∅ for some i ∈ {1, 2, . . . , s + t}. Let w ∈ W. Note that w /∈ H(i). By Proposition 3.1, there exist two adjacent vertices h(i,j) and h(i,k) in H satisfying dH(h(i,j) , h) = dH(h(i,k) , h). So, we have

\[d_H(h_{(i,j)}, w) = d_H(h_{(i,j)}, h) + d_H(h, w)\]
= \(d_H(h_{(i,k)}, h) + d_H(h, w)\)
= \(d_H(h_{(i,k)}, w)\)

Therefore, we obtain r(h(i,j) | W) = r(h(i,k) | W), a contradiction.

(ii) W ∩ H(j) = ∅ for every j ∈ {s + t + 1, s + t + 2, . . . , n} Suppose that there exists j ∈ {s + t + 1, s + t + 2, . . . , n} such that W ∩ H(j) 6= ∅. Let w ∈ H(j) be an element of W. We consider W⁰ = W \ {w}. We will show that W⁰ is still a local resolving set of H.

By considering (i), let S = {x ∈ W | x ∈ H(i), 1 ≤ i ≤ s + t}. Note that, by the definition of W⁰ , we also have that S ⊆ W⁰ . Let x, y be two adjacent vertices in V (H) \ W⁰ . So, there exists i ∈ {1, 2, . . . , n} such that x, y ∈ H? i . We distinguish two cases.

Case 1. i ∈ {1, 2, . . . , s + t}.

By (i), we have that x, y are locally resolved by vertices in S. It follows that both vertices are locally resolved by W⁰ .

Case 2. \(i \in \{s+t+1, s+t+2, \dots, n\}\).

Since every \(H_i\) with \(i \in \{s+t+1, s+t+2, \ldots, n\}\) is bipartite, we have \(lmd(H_i) = 1\). Let \(B_i\) be a local basis of \(H_i\). Then for every \(v \in V(H_i)\), there exists \(B_i\) where \(B_i = \{v\}\). Thus, \(d_{H_i}(x',v) \neq d_{H_i}(y',v)\) for every two adjacent vertices \(x',y' \in V(H_i) \setminus \{v\}\). Let v=h, we obtain that \(d_{H_i}(x',h) \neq d_{H_i}(y',h)\). Consider two vertices \(x,y \in H_i^*\) which are corresponded to \(x',y' \in V(H_i) \setminus \{v\}\), respectively. For any \(z \in W'\), we obtain that

\[d_{H}(x,z) = d_{H}(x,h) + d_{H}(h,z)\] \[= d_{H_{i}}(x',h) + d_{H}(h,z)\] \[\neq d_{H_{i}}(y',h) + d_{H}(h,z)\] \[= d_{H}(y,h) + d_{H}(h,z)\] \[= d_{H}(y,z).\]

So, \(r(x|W') \neq r(y|W')\). Then every two adjacent vertices \(x, y \in V(H) \setminus W'\) are locally resolved by vertices in W'. In both cases, we obtain that W' is a local resolving set of H, a contradiction.

Lemma 3.2. Let W be a local basis of H. If s > 1 or \(t \ge 1\), then \(h \notin W\).

Proof. Let W be a local basis of H where \(h \in W\). We consider \(W' = W \setminus \{h\}\). We will show that W' is also a local resolving set of H.

Let x and y be two adjacent vertices in \(V(H) \setminus W'\). By considering properties in Lemma 3.1, we have that x and y are locally resolved by vertices in W'. Thus, we have a contradiction. \(\square\)

From proposition and lemmas above we have the following theorem.

Theorem 3.1. For \(n \geq 2\) and \(i \in \{1, 2, ..., n\}\), let \(H_i\) be a simple connected graph of order at least 2 containing a subgraph J and \(\mathcal{H} = \{H_1, H_2, ..., H_n\}\). Let \(J = K_1\) where \(V(J) = \{h\}\). Let \(S = \{A \in \mathcal{H} \mid A \text{ is not bipartite and there exists a local basis of } A \text{ containing } h\}\) and \(\mathcal{T} = \{A \in \mathcal{H} \mid A \text{ is not bipartite and every local basis of } A \text{ does not contain } h\}\). If s = |S|, t = |T| and the first s + t elements in \(\mathcal{H}\) are from \(S \cup \mathcal{T}\), then

\[lmd(Subgraph - Amal\{\mathcal{H}; J\}) = \begin{cases} 1, & s = t = 0; \\ lmd(H_s), & s = 1 \text{ and } t = 0; \\ \sum_{i=1}^{s+t} lmd(H_i) - s, & s \ge 2 \text{ or } t \ge 1. \end{cases}\]

Proof. Let \(H \cong Subgraph - Amal\{\mathcal{H}; J\}\). If s = t = 0, then every graph \(H_i\) is bipartite. It follows that H is also bipartite. Okamoto et al. [23] have been proved that the local metric dimension of any bipartite graphs is 1.

Now, assume \(s \ge 1\) or \(t \ge 1\). Let \(\mathcal{H} = \{H_1, H_2, \dots, H_s, H_{s+1}, \dots, H_{s+t}, H_{s+t+1}, \dots, H_n\}\) where \(\mathcal{S} = \{H_1, H_2, \dots, H_s\}\) and \(\mathcal{T} = \{H_{s+1}, H_{s+2}, \dots, H_{s+t}\}\). We have two cases.

Case 1. s = 1 and t = 0.

First, we will show that \(lmd(H) \leq lmd(H_s)\) by constructing a local resolving set with \(lmd(H_s)\) vertices. Let \(B_s\) be a local basis of \(H_s\) containing h. We define \(B_s' = B_s \setminus \{h\}\) and \(W = \{h_{(s,t)} \mid h_t \in B_s'\} \cup \{h\}\). Let us consider any two adjacent vertices \(h_{(i,j)}, h_{(i,k)} \in V(H) \setminus W\). If i = s = 1, then \(h_j\) and \(h_k\) are locally resolved by \(B_s\), which implies \(h_{(1,j)}, h_{(1,k)}\) are locally resolved by W. Now, we assume that \(i \in \{2, 3, \dots, n\}\). We obtain that \(H_i\) is a bipartite graph. Since there exists a local basis of \(H_i\) containing exactly one vertex h, then \(h_{(i,j)}, h_{(i,k)}\) of H are locally resolved by \(h \in W\). Thus, W is a local resolving set of H.

Next, we will show that \(lmd(H) \ge lmd(H_s)\). Suppose that \(lmd(H) \le (lmd(H_s)) - 1\). Let S be a local basis of H. So, \(|S| \le lmd(H_s) - 1\). By Lemma 3.1 (ii), \(S \cap H_i = \emptyset\), \(i \in \{2, 3, \dots, n\}\). We define a subset U of \(V(H_s)\) as \(\{h\} \cup \{h_j \mid h_{(s,j)} \in S\}\). Since \(|U| = |S| \le lmd(H_s) - 1\), there exist two adjacent vertices \(h_k, h_l \in V(H_s)\) satisfying \(r(h_k \mid U) = r(h_l \mid U)\). It follows that \(r(h_{(s,k)} \mid S) = r(h_{(s,l)} \mid S)\), a contradiction.

Case 2. \(s \ge 2\) or \(t \ge 1\).

First, we will show that \(lmd(H) \leq \sum_{i=1}^{s+t} lmd(H_i) - s\) by constructing a local resolving set with \(\sum_{i=1}^{s+t} lmd(H_i) - s\) vertices. Since \(s \geq 2\) or \(t \geq 1\) for \(i \in \{1, 2, \dots, s+t\}\), \(H_i\) is not bipartite and \(lmd(H_i) > 1\).

• \(s \ge 1\) and \(i \in \{1, 2, ..., s\}\)Let \(B_i\) be a local basis of \(H_i\) containing h. Then we define \(W_i = \{h_{(i,j)} | h_j \in B_i \setminus \{h\}\}\).
• \(t \ge 1\) and \(i \in \{s+1, s+2, \dots, s+t\}\)Let \(C_i\) be a local basis of \(H_i\). We define \(W_i = \{h_{(i,j)} | h_j \in C_i\}\).

Now, define \(W = \bigcup_{i=1}^{s+t} W_i\). Note that W satisfies Lemmas 3.1 and 3.2. Let us consider any two adjacent vertices \(x, y \in V(H) \setminus W\). Note that there exists \(i \in \{1, 2, ..., n\}\) such that \(x, y \in H_i^*\).

• \(s \neq 0\) and \(i \in \{1, 2, ..., s\}\)If \(d_H(x, h) \neq d_H(y, h)\), then it is clear that x, y are locally resolved by vertices in \(W \setminus W_i\). Otherwise, x, y are locally resolved by vertices in \(W_i\).
• \(t \neq 0\) and \(i \in \{s+1, s+2, \dots, s+t\}\)Then x, y are locally resolved by vertices in \(W_i\).
• s+t < n and i ∈ {s+t+1, s+t+2,...,n}</li> Since x, y are locally resolved by the vertex h, it implies that they are locally resolved by all vertices in W.

Therefore, W is a local resolving set of H.

Next, suppose that \(lmd(H) \leq (\sum_{i=1}^{s+t} lmd(H_i) - s) - 1\). Let W be a local basis of H. By Lemma 3.1 (ii) and Lemma 3.2, we have \(W \cap H(j) = \emptyset\) for every \(j \in \{s+t+1, s+t+2, \ldots, n\}\) and \(h \notin W\). Since \(|W| \leq \sum_{i=1}^{s+t} lmd(H_i) - s - 1\), we obtain two possibilities.

• 1. There exists \(i \in \{1, 2, \dots, s\}\) such that \(|W \cap H_i^\star| \leq lmd(H_i) 2\)Let \(W_i = W \cap H_i^\star\) and \(S_i = \{h_j \mid h_{(i,j)} \in W_i\} \cup \{h\}\). Since \(|S_i| < lmd(H_i)\), then there exists two adjacent vertices \(h_k, h_l\) in \(H_i\) which are not locally resolved by \(S_i\). It follows that \(h_{(i,k)}, h_{(i,l)}\) are not locally resolved by \(W_i\), which implies \(r(h_{(i,k)} \mid W) = r(h_{(i,l)} \mid W)\).
• 2. There exists \(i \in \{s+1, s+2, \ldots, s+t\}\) such that \(|W \cap H_i^\star| \leq lmd(H_j) 1\)Let \(W_i = W \cap H_i^\star\) and \(S_i = \{h_j \mid h_{(i,j)} \in W_i\} \cup \{h\}\). Note that, \(|S_i| = lmd(H_i)\). However, every local basis of \(H_i\) does not contain h. It follows that \(S_i\) is not a local resolving set of \(H_i\). Then there exists two adjacent vertices \(h_k, h_l\) in \(H_i\) which are not locally resolved by \(S_i\). It follows that \(h_{(i,k)}, h_{(i,l)}\) are not locally resolved by \(W_i\), which implies \(r(h_{(i,k)} \mid W) = r(h_{(i,l)} \mid W)\).

By both possibilities above, we have a contradiction.

4. Edge Amalgamation

For \(n \in \mathbb{N}\) and \(i \in \{1, 2, ..., n\}\), let \(H_i\) be a simple connected graph of order \(k_i \geq 2\) containing a connected subgraph J of order p where \(1 \leq p < k_i\). In this section, let \(\mathcal{H} = \{H_1, H_2, ..., H_n\}\) where \(J \cong P_2\). Since \(P_2\) has only one edge, the graph \(Subgraph - Amal\{\mathcal{H}, J\}\) then is called as an edge amalgamation graph.

Let \(V(H_i) = \{h_1, h_2, \dots, h_{k_i}\}\) where \(V(J) = \{h_1, h_2\}\). In this section, we denote \(H \cong Subgraph - Amal\{\mathcal{H}; J\}\). We define \(V(H) = \{h_1, h_2\} \cup \{h_{(i,j)} | 1 \le i \le n, \ 3 \le j \le k_i\}\), \(H(i) = \{h_{(i,j)} | 3 \le j \le k_i\}\), and \(H_i^{\star} = \{h_1, h_2\} \cup H(i)\).

According to Theorem 2.1, we obtain the bounds for the local metric dimension of any edge amalgamation graphs, which can be seen in theorem below.

Theorem 4.1. For \(n \geq 2\) and \(i \in \{1, 2, ..., n\}\), let \(H_i\) be a simple connected graph of order at least 3 and \(\mathcal{H} = \{H_1, H_2, ..., H_n\}\). Then

\[\sum_{i=1}^{n} lmd(H_i) - 2n \le lmd(Subgraph - Amal\{\mathcal{H}; P_2\}) \le \sum_{i=1}^{n} lmd(H_i).\]

In this section, we will show that all values between the lower and upper bound in Theorem 4.1 are achievable. In order to do so, we need to determine the local metric dimension of graphs \(G_3\), \(G_4\), and \(G_5\). The graph \(G_3\) and its complement are illustrated in Figures 4. Meanwhile the graphs \(G_4\) and \(G_5\) can be seen in Figures 5 and 6, respectively.

First, let us consider the graph \(G_3\). Let \(N_3 = \{a_1, a_2\}\), \(O_3 = \{a_3, a_4\}\), \(P_3 = \{a_5, a_6\}\), \(R_3 = \{a_7, a_8\}\), and \(S_3 = \{a_9, a_{10}, a_{11}, a_{12}\}\). Now, we are ready to determine the local metric dimension of \(G_3\).

Lemma 4.1. Let \(G_3\) be a connected graph as stated in Figure 4. Then \(lmd(G_3) = 4\). Moreover the set \(\{a_1, a_2, a_7, a_8\}\) is a local basis of \(G_3\).

Proof. Since \(G_3\) contains an odd cycle, we have \(lmd(G_3) > 1\). Next, we will show that there is no local resolving set of \(G_3\) with 2 elements. Suppose that W be a local resolving set of \(G_3\) with

Figure 4. Graph G³ (left) and its complement (right)

|W| = 2. We obtain two cases.

Case 1. W ∩ S³ = ∅.

Then there exist two distinct vertices x, y ∈ O³ ∪ P³ which are adjacent to both vertices in W. Therefore, we have r(x | W) = (1, 1) = r(y | W).

Case 2. W ∩ S³ 6= ∅.

Let W = {x, y} where x ∈ S3. If y ∈ N³ ∪ O3, then we have r(a⁵ | W) = (1, 1) = r(a⁶ | W). Otherwise, we have r(a³ | W) = (1, 1) = r(a⁴ | W). By all cases above, we obtain that W is not local resolving set of G3. Therefore, we can conclude that lmd(G3) ≥ 3. However, we will also show that there is no local resolving set of G³ with cardinality 3. Suppose that W⁰ be a local resolving set of G³ with |W⁰ | = 3. Note that, at least one vertices of S³ are not in W⁰ . Without loss of generality, let a⁹ ∈/ W⁰ . Let |W⁰ ∩ S3| = j where j ∈ {0, 1, 2, 3}. Then there exist j + 1 vertices z1, . . . , zj+1 ∈ O³ ∪ P³ which are adjacent to every vertex in W⁰ . If j = 0, we have r(z¹ | W⁰ ) = (1, 1) = r(a⁹ | W⁰ ). Otherwise, r(z¹ | W⁰ ) = (1, 1) = r(z² | W⁰ ). Thus, W⁰ is not local resolving set of G3. Since there is no local resolving set of G³ with cardinality 3, we obtain that lmd(G3) ≥ 4.

Next, we will show that lmd(G3) ≤ 4. Define W" = {a1, a2, a7, a8}. The representation of all vertices in G³ with respect to W" are as follows.

\[r(a_1|W") = (0,1,2,1)\] \(r(a_3|W") = (2,1,1,1)\) \(r(a_9|W") = (1,1,1,1)\) \(r(a_2|W") = (1,0,1,2)\) \(r(a_4|W") = (1,2,1,1)\) \(r(a_{10}|W") = (1,1,1,1)\) \(r(a_{10}|W") = (1,1,1,1)\) \(r(a_{10}|W") = (1,1,1,1)\) \(r(a_{11}|W") = (1,1,1,1)\) \(r(a_{11}|W") = (1,1,1,1)\) \(r(a_{11}|W") = (1,1,1,1)\)

Since there are no two adjacent vertices of G³ having the same representation, we conclude that

W" is a local resolving set of \(G_3\).

Figure 5. Graph \(G_4\)

Next, let us consider the graph \(G_4\). Let \(N_4 = \{b_1, b_2, b_3\}\), \(O_4 = \{c_i \mid 1 \le i \le t, t \ge 1\}\), \(P_4 = \{d_1, d_2, d_3\}\). Now, we are ready to determine the local metric dimension of \(G_4\).

Lemma 4.2. Let \(G_4\) be a connected graph as stated in Figure 5. Then \(lmd(G_4) = 4\). Moreover, every local resolving set of \(G_4\) contains at least two vertices of \(N_4\) and at least two vertices of \(P_4\).

Proof. Let W be a local resolving set of \(G_4\). If \(|W \cap N_4| \le 1\) (or \(|W \cap P_4| \le 1\)), then there exist two distinct vertices \(x, y \in N_4\) (or \(x, y \in P_4\)) which are not element of W. Since x and y are adjacent, and for every \(z \in V(G_4) \setminus \{x, y\}\), \(d_{G_4}(x, z) = d_{G_4}(y, z)\), we have \(r(x \mid W) = r(y \mid W)\), a contradiction. So, it must be \(|W \cap N_4| \ge 2\) and \(|W \cap P_4| \ge 2\), which implies \(lmd(G_4) \ge 4\).

Next, we will show that \(lmd(G_4) \leq 4\). Define \(W' = \{b_1, b_2, d_1, d_2\}\). Let us consider two adjacent vertices \(u, v \in V(G_4) \setminus W'\). If \(d_{G_4}(u, b_1) \neq d_{G_4}(v, b_1)\), then we obtain \(r(u \mid W') \neq r(v \mid W')\). Otherwise, we have \(u = b_3\) and \(v = c_1\). Since \(d_{G_4}(u, d_1) = d_{G_4}(v, d_1) + 1\), we also obtain \(r(u \mid W') \neq r(v \mid W')\). Thus, W' is a local resolving set of \(G_4\).

Figure 6. Graph \(G_5\)

Lemma 4.3. Let \(G_5\) be a connected graph as stated in Figure 6. Then \(Imd(G_5) = 2\) where \(\{e_5, e_6\}\) is a local basis of \(G_5\). If a local resolving set B of \(G_5\) contains \(e_1\) or \(e_2\), then \(|B| \geq 3\). Moreover, the set \(\{e_1, e_2, e_3\}\) is a local resolving set of \(G_5\).

Proof. Since \(G_5\) contains an odd cylce, we have \(Imd(G_5) > 1\). Next, we will construct a local resolving set of \(G_5\) with 2 vertices. Define \(W = \{e_5, e_6\}\). The representation of all vertices in \(G_5\) with respect to W are as follows.

\[r(e_1|W) = (2,1)\] \(r(e_3|W) = (2,2)\) \(r(e_5|W) = (0,1)\) \(r(e_7|W) = (1,1)\) \(r(e_2|W) = (1,2)\) \(r(e_4|W) = (2,2)\) \(r(e_6|W) = (1,0)\) \(r(e_8|W) = (1,1)\)

Since there are no two adjacent vertices having the same representation, we conclude that W is a local resolving set of \(G_5\).

Next, we will show that every local basis B of \(G_5\) satisfies \(e_i \notin B\) for \(i \in \{1, 2\}\). Suppose that \(e_1 \in B\) or \(e_2 \in B\). If \(e_1, e_2 \in B\), then two adjacent vertices \(e_3\) and \(e_8\) are not locally resolved by B, a contradiction. Now, we assume that either \(e_1 \in B\) or \(e_2 \in B\). For \(i \in \{1, 2\}\) and \(j \in \{1, 2\} \setminus \{i\}\), let \(e_i \in B\) and \(e_j \notin B\). Let \(D = \{e_3, e_4, e_{4+i}\}\). If \(B \cap D \neq \emptyset\), then two adjacent vertices \(e_j\) and \(e_8\) are not locally resolved by B. Otherwise, two adjacent vertices \(e_j\) and \(e_3\) are not locally resolved by B. Thus, we have that B is not local resolving set of \(G_5\).

Now, let \(S = \{e_1, e_2, e_3\}\). The representation of all vertices in \(G_5\) with respect to S are as follows.

\[r(e_1|S) = (0,1,1)\] \(r(e_3|S) = (1,1,0)\) \(r(e_5|S) = (2,1,2)\) \(r(e_7|S) = (1,1,1)\) \(r(e_2|S) = (1,0,1)\) \(r(e_4|S) = (1,1,2)\) \(r(e_6|S) = (1,2,2)\) \(r(e_8|S) = (1,1,1)\)

Since there are no two adjacent vertices having the same representation, we conclude that S is a local resolving set of \(G_5\).

Now, we are ready to show that all values between the lower and upper bound in Theorem 4.1 are achievable, which can be seen in theorem below.

Theorem 4.2. For \(n \geq 2\) and \(i \in \{1, 2, ..., n\}\), there exist simple connected graph \(H_i\) of order at least 3 and \(\mathcal{H} = \{H_1, H_2, ..., H_n\}\) such that \(lmd(Subgraph - Amal\{\mathcal{H}; P_2\}) = k\) for every integer k satisfying \(\sum_{i=1}^{n} lmd(H_i) - 2n < k < \sum_{i=1}^{n} lmd(H_i)\).

Proof. Let us consider a finite collection \(\mathcal{H}=\{H_1,H_2,\ldots,H_n\}\) where \(H_i=G_3\). Let \(a_1a_2\) be the terminal edge from every \(H_i\) and \(H\cong Subgraph-Amal\{\mathcal{H};P_2\}\). We will show that \(lmd(H)=\sum_{i=1}^n lmd(H_i)-2n\). By Theorem 2.1, we only need to show that \(lmd(H)\leq\sum_{i=1}^n lmd(H_i)-2n\). Define \(W=\bigcup_{i=1}^n \{a_{(i,7)},a_{(i,8)}\}\). Let us consider any two adjacent vertices \(x_1,x_2\in V(H)\setminus W\). Then there exists \(i\in\{1,2,\ldots,n\}\) such that \(x_1,x_2\in H_i^*\). Let \(y_1,y_2\in V(H_i)\) which are corresponded to \(x_1,x_2\in V(H)\), respectively. It is clear that \(y_1\) is also adjacent to \(y_2\) in \(H_i\). If \(a_7\) or \(a_8\) is locally resolves \(y_1\) and \(y_2\), then it follows that \(x_1\) and \(x_2\) are locally resolves by W. Otherwise, \(y_1\) and \(y_2\) are locally resolved by \(a_1\) or \(a_2\).

• \(y_1\) and \(y_2\) are locally resolved by \(a_1\)Then for \(l \in \{1, 2, ..., n\} \setminus \{i\}\), we have

\[d_H(x_1, a_{(l,8)}) = d_H(x_1, a_1) + d_H(a_1, a_{(l,8)})\] \[= d_{H_i}(y_1, a_1) + d_{H_i}(a_1, a_8)\] \[\neq d_{H_i}(y_2, a_1) + d_{H_i}(a_1, a_8)\] \[= d_H(x_2, a_1) + d_H(a_1, a_{(l,8)})\] \[= d_H(x_2, a_{(l,8)}).\]

• \(y_1\) and \(y_2\) are locally resolved by \(a_2\)Then for \(l \in \{1, 2, ..., n\} \setminus \{i\}\), we have

\[d_{H}(x_{1}, a_{(l,7)}) = d_{H}(x_{1}, a_{2}) + d_{H}(a_{2}, a_{(l,7)})\] \[= d_{H_{i}}(y_{1}, a_{2}) + d_{H_{i}}(a_{2}, a_{7})\] \[\neq d_{H_{i}}(y_{2}, a_{2}) + d_{H_{i}}(a_{2}, a_{7})\] \[= d_{H}(x_{2}, a_{2}) + d_{H}(a_{2}, a_{(l,7)})\] \[= d_{H}(x_{2}, a_{(l,7)}).\]

Therefore, W is a local resolving set of H. It implies that \(lmd(H) = \sum_{i=1}^{n} lmd(H_i) - 2n\).

To obtain an edge amalgamation graph whose local metric dimension is \(k = \sum_{i=1}^{n} lmd(H_i) - 2n + q\) for \(1 \le q \le 2n\), we replace some \(H_i\) in \(\mathcal{H}\) by \(G_4\) or \(G_5\) according to the parity of q. For \(l \in \{1, 2, \ldots, n\}\), we distinguish two cases.

Case 1. q = 2l

Let \(\mathcal{H}' = \{H'_1, H'_2, \dots, H'_n\}\) be a finite collection which is obtain from \(\mathcal{H}\) by replacing l elements of \(\mathcal{H}\) by \(G_4\). Choose the terminal edge \(c_t c_{t+1}\) for \(G_4\) and \(a_1 a_2\) for \(G_3\).

Case 2. q = 2l - 1

Let \(\mathcal{H}' = \{H'_1, H'_2, \dots, H'_n\}\) be a finite collection which is obtain from \(\mathcal{H}\) by replacing l-1 elements of \(\mathcal{H}\) by \(G_4\) and an element of \(\mathcal{H}\) by \(G_5\). Choose the terminal edge \(e_1e_2\) for \(G_5\), \(c_tc_{t+1}\) for \(G_4\), and \(a_1a_2\) for \(G_3\).

By Lemma 4.1, the graph \(G_3\) has a local basis \(S_3\) containing \(a_1, a_2\). However, by Lemmas 4.2 and 4.3, \(G_4\) and \(G_5\) do not have a local basis containing \(c_t, c_{t+1}\) and \(e_1, e_2\), respectively. So, for \(G_4\) and \(G_5\), we consider a minimum resolving set \(S_4\) and \(S_5\), respectively, containing two vertices of their terminal edge. Note that, \(|S_4| \geq lmd(G_4) + 2\) and \(|S_5| \geq lmd(G_5) + 1\). Thus, by using the similar argument with the proof of Lemma 2.1, the graphs \(G_3, G_4\), and \(G_5\) must contribute at least \(lmd(G_3) - 2\), \(lmd(G_4)\), and \(lmd(G_5) - 1\) vertices to a resolving set of \(Subgraph - Amal\{\mathcal{H}', P_2\}\), respectively.

Now, we will construct a resolving set of \(Subgraph - Amal\{\mathcal{H}', P_2\}\) with \(\sum_{i=1}^n lmd(H_i) - 2n + q\) vertices. Let \(B_3\), \(B_4\), and \(B_5\) be the set of vertices in \(Subgraph - Amal\{\mathcal{H}', P_2\}\) which are corresponded to vertices \(a_7\) and \(a_8\) of \(G_3\), vertices \(b_1\), \(b_2\), \(d_1\), and \(d_2\) of \(G_4\), and vertex \(e_3\) of

\(G_5\), respectively. Then, define \(B=B_3\cup B_4\cup B_5\). Note that, for q is even, we have \(B_5=\emptyset\). Let \(H\cong Subgraph-Amal\{\mathcal{H}',P_2\}\). Let us consider any two adjacent vertices \(x_1,x_2\in V(H)\setminus B\). Then there exists \(i\in\{1,2,\ldots,n\}\) such that \(x_1,x_2\in H_i'^\star\). Let \(H_i'\cong G_j\) where \(j\in\{3,4,5\}\). If \(x_1,x_2\) are resolved by \(B_j\), then we are done. Otherwise, \(x_1,x_2\) then are resolved by a vertex in terminal edge of \(H_i'\). We distinguish two cases.

Case 1. \(H'_i \cong G_3\)

Let \(y_1, y_2 \in V(H'_i)\) which are corresponded to \(x_1, x_2 \in V(H)\), respectively. Then it is clear that \(a_1\) or \(a_2\) is locally resolves \(y_1\) and \(y_2\). Note that, in H, the vertex \(a_1\) of \(H'_i\) can be identified by \(c_t\) or \(c_{t+1}\) of \(H'_r\) where \(H'_r \cong G_4\). So, \(x_1, x_2\) are locally resolved by vertices in \(B_4\).

Case 2. \(H_i' \cong G_5\)

Let \(y_1, y_2 \in V(H'_i)\) which are corresponded to \(x_1, x_2 \in V(H)\), respectively. Then it is clear that \(e_1\) or \(e_2\) is locally resolves \(y_1\) and \(y_2\). Note that, in H, the vertex \(e_1\) of \(H'_i\) can be identified by \(a_1\) or \(a_2\) of \(H'_r\) where \(H'_r \cong G_3\), or by \(c_t\) or \(c_{t+1}\) of \(H'_r\) where \(H'_r \cong G_4\). So, \(x_1, x_2\) are locally resolved by vertices in \(B_3\) or \(B_4\).

Conclusion

Let \(\mathcal{H} = \{H_1, H_2, \dots, H_n\}\) be a finite collection of simple connected graphs, where \(H_i\) is a graph containing a connected subgraph J. In this paper, we consider the subgraph-amalgamation graphs \(Subgraph - Amal\{\mathcal{H}; J\}\). This graph is constructed by taking all elements of \(\mathcal{H}\), then identifying all of them on J. We provide the lower and upper bounds of \(lmd(Subgraph - Amal\{\mathcal{H}; J\})\) for any structures of J. These bounds are functions of \(lmd(H_i)\) \((1 \le i \le n)\). We also provide some properties of \(Subgraph - Amal\{\mathcal{H}; J\}\) whose local metric dimension is equal to some values, including the upper and lower bound values.

Furthermore, we consider \(Subgraph-Amal\{\mathcal{H};J\}\) for certain structure of J. For J is a vertex \((J=K_1)\), we determine an exact value of the local metric dimension of \(Subgraph-Amal\{\mathcal{H};J\}\). In case J is an edge \((J=P_2)\), we provide the lower and upper bounds of \(Imd(Subgraph-Amal\{\mathcal{H};J\})\). Moreover, we show that all values between those bounds are achievable.

For future work, we provide an interesting question that is whether all between the lower and upper bounds in Theorem 2.1 are achievable if the order of J is at least 3. The problem is stated as follows.

Problem 1. Let J be a connected graph of order \(p \geq 3\). Does there exist \(\mathcal{H} = \{H_1, H_2, \dots, H_n\}\) where \(H_i\) is a connected graph containing J, such that for every integer t with \(\sum_{i=1}^n lmd(H_i) - pn < t < \sum_{i=1}^n lmd(H_i)\), we have \(lmd(Subgraph - Amal\{\mathcal{H}; J\}) = t\)?

Acknowledgement

The authors are thankful to the anonymous referee for some comments that helped to improve the presentation of the manuscript.

References

• [1] G. Abrishami, M.A. Henning, and M. Tavakoli, Local metric dimension for graphs with small clique numbers, Discrete Math. 345 (2022), 112763.
• [2] S. Akhter and R. Farooq, Metric dimension of fullerene graphs, Electron. J. Graph Theory Appl. 7 (1) (2019), 91–103.
• [3] G.A. Barragan-Ram ´ ´ırez, A. Estrada-Moreno, Y. Ram´ırez-Cruz, and J.A. Rodr´ıguez-Velazquez, The local metric dimension of the lexicographic product of graphs, ´ Bull. Malays. Math. Sci. Soc. 42 (2019), 2481–2496.
• [4] G.A. Barragan-Ram ´ ´ırez and J.A. Rodr´ıguez-Velazquez, The local metric dimension of the ´ strong product graphs, Graph Combin. 32 (2016), 1263–1278.
• [5] Z. Beerliova, F. Eberhard, T. Erlebach, A. Hall, M. Hoffmann, M. Mihalak, and L.S. Ram, ´ Network discovery and verification, IEEE Journal on Selected Areas in Communications 24(12) (2006), 2168–2181.
• [6] P.S. Buszkowski, G. Chartrand, C. Poisson, and P. Zhang, On k-dimensional graphs and their bases, Period. Math. Hungar. 46(1) (2003), 9–15.
• [7] J. Caceres, C. Hernando, M. Mora, M.L. Puertas, I.M. Pelayo, C. Seara, and D.R. Wood, On the metric dimension of some families of graphs, Electron. Notes Discrete Math. 22 (2005), 129–133.
• [8] J. Caceres, C. Hernando, M. Mora, M.L. Puertas, I.M. Pelayo, C. Seara, and D.R. Wood, On the metric dimension of cartesian product of graphs, SIAM J. Discrete Math. 21(12) (2007), 423–441.
• [9] G. Chartrand, L. Eroh, M.A. Johnson, and O.R. Oellermann, Resolvability in graphs and the metric dimension of a graphs, Discrete Appl. Math. 105 (2000), 99–113.
• [10] G. Chartrand and P. Zhang, The theory and application of resolvability in graphs, Comput. Math. Appl. 39 (2000), 19–28.
• [11] J.A. Cynthia and Ramya, The local metric dimension of torus network, International Journal of Pure and Applied Mathematics 120(7) (2018), 225–233.
• [12] M. Fehr, S.Gosselin, and O.R. Oellermann, The metric dimension of Cayley digraphs, Discrete Math. 306 (2006), 31–40.
• [13] D. Fitriani, A. Rarasati, S.W. Saputro, E.T. Baskoro, The local metric dimension of split and unicyclic graphs, Indones. J. Combin. 6(1) (2022), 50–57.
• [14] W. Goodard, Mastermind revisited, J. Combin. Math. Combin. Comput. 51 (2003), 215–220.

• [15] F. Harary and R.A. Melter, On the metric dimension of a graph, Ars. Combin. 2 (1976), 191–195.
• [16] C. Hernando, M. Mora, I.M. Pelayo, C. Seara, and D.R. Wood, Extremal Graph Theory for Metric Dimension and Diameter, The Electron. J. Combin. 17 (2010), ]R30.
• [17] H. Iswadi, E.T. Baskoro, and R. Simanjuntak, On the metric dimension of corona product of graphs, Far East J. Math. Sci. 52(2) (2011), 155–170.
• [18] M. Jannesari and B. Omoomi, Characterization of n-vertex graphs with metric dimension n − 3, Math. Bohem. 134 (2011), 1–23.
• [19] S. Khuller, B. Raghavachari, and A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math. 70(3) (1996), 217–229.
• [20] S. Klavzar and M. Tavakoli, Local metric dimension of graphs: Generalized hierarchical ˇ product and some applications, Appl. Math. Comput. 364 (2020), 124676.
• [21] S. Klavzar and S. Zemljic, On distances in Sierpi ˇ nski graphs: Almost-extreme vertices and ´ metric dimension, Appl. Anal. Discrete Math. 7 (2013), 72–82.
• [22] P. Manuel, B. Rajan, I. Rajasingh, and C. Monica M., On minimum metric dimension of honeycomb networks, J. Discrete Algorithms. 6 (2008), 20–27.
• [23] F. Okamoto, B. Phinezy, and P. Zhang, The local metric dimension of a graph Math. Bohem., 135 (2010), 239–255.
• [24] C. Poisson and P. Zhang, The metric dimension of unicyclic graphs, J. Combin. Math. Combin. Comput. 40 (2002), 17–32.
• [25] J.A. Rodr´ıguez-Velazquez, G.A. Barrag ´ an-Ram ´ ´ırez, and C.G. Gomez, On the local metric ´ dimension of corona product graphs Bull. Malays. Math. Sci. Soc., 39 (2013), 157–173.
• [26] J.A. Rodr´ıguez-Velazquez, C.G. G ´ omez, and G.A. Barrag ´ an-Ram ´ ´ırez, Computing the local metric dimension of a graph from the local metric dimension of primary subgraphs, Comput. Math. 92(4) (2015), 686–693.
• [27] J.A. Rodr´ıguez-Velazquez, D. Kuziak, I.G. Yero, and J.M. Sigarreta, The metric dimension ´ of strong product graphs, Carpathian J. Math. 31(2) (2015), 261–268.
• [28] S.W. Saputro, On local metric dimension of (n−3)-regular graph, J. Combin. Math. Combin. Comput. 98 (2016), 43–54.
• [29] S.W. Saputro, On the metric dimension of biregular graph, J. Inform. Process. 25 (2017), 634–638.
• [30] S.W. Saputro, N. Mardiana, and I.A. Purwasih, The metric dimenison of comb product graphs, Math. Vesnik 69 (2017), 248–258.

• [31] S.W. Saputro, R. Simanjuntak, S. Uttunggadewa, H. Assiyatun, and E.T. Baskoro, The metric dimension of the lexicographic product of graphs, Discrete Math. 313 (2013), 1045–1051.
• [32] B. Shanmukha, B. Sooryanarayana, and K.S. Harinath, Metric dimension of wheels, Far East J. Appl. Math. 8:3 (2002), 217–229.
• [33] R. Simanjuntak, S. Uttunggadewa, and S.W. Saputro, Metric dimension for amalgamation of graphs, LNCS 8986 Combin. Algorithms. (2015), 330–337.
• [34] P.J. Slater, Leaves of trees, Proc. 6th Southeastern Conf. on Combinatorics, Graph Theory, and Computing., Congr. Numer. 14 (1975), 549–559.
• [35] T. Vetr´ık and A. Ahmad, Computing the metric dimension of the categorial product of some graphs Int. J. Comput. Math., (2015)
• [36] I. Tomescu and I. Javaid, On the metric dimension of the Jahangir graph, Bull. Math. Soc. Sci. Math. Roumanie 4 (2007), 371–376.
• [37] I.G. Yero, D. Kuziak, and J.A. Rodr´ıguez-Velazquez, On the metric dimension of corona ´ products graphs, Comput. Math. Appl. 61:9 (2011), 2793–2798.