Electronic Journal of Graph Theory and Applications 12 .
, 125Ae146 The local metric dimension of amalgamation of Fitriani.
Saputro Combinatorial Mathematics Research Group.
Faculty of Mathematics and Natural Sciences Institut Teknologi Bandung.
Indonesia.
fitriani@gmail.
com, suhadi@itb.
Abstract 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 OO N and i OO .
, 2, .
, .
, let Hi 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 Oe Amal{H.
J}, is a graph obtained by identifying all elements of H in 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 We also determine the local metric dimension of Subgraph Oe Amal{H.
J} for J is either K1 or P2 .
Keywords: local basis, local metric dimension, local resolving set, subgraph-amalgamation Mathematics Subject Classification : 05C12, 05C76 DOI: 10.
5614/ejgta.
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 .
, .
, 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.
The local metric dimension of amalgamation of graphs Fitriani and S.
Saputro W = .
1 , w2 , .
, wk } be a subset of V (G).
The representation of v with respect to W is defined as the k-tuple r.
| W ) = .
G .
, w1 ), dG .
, w2 ), .
, dG .
, 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 .
and independently by Harary and Melter .
Since then, this topic has been widely investigated.
All graphs with certain metric dimension have been studied in .
, 16, .
The metric dimension of certain classes of graph is also determined, including trees .
, 19, .
, cycles .
, unicyclic graphs .
, wheels .
, 7, .
, fans .
Cayley graphs .
Jahangir graphs .
, honeycomb networks .
, regular graphs .
SierpinAski graphs .
, amalgamation of graphs .
, and fullerene graphs .
This topic also has been arised in many applications, such as network discovery and verification .
, robotic navigation .
, .
, and mastermind .
Some other results on metric dimension can be seen in .
, 17, 19, 27, 30, 31, 35, .
In this paper, we consider a variance of metric dimension, namely local metric dimension.
this version, two different vertices may have the same representation with respect to an ordered subset W of V (G).
In case r.
| W ) 6= r.
| 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 O lmd(G) O dim(G).
The local metric dimension problem was introduced by Okamoto et al.
They proved that bipartite graphs are the only graphs having local metric dimension one.
Moreover, they also showed that lmd(G) = n Oe 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 Oe 2.
The local metric dimension of some certain particular graphs also has been determined, including graphs with small clique number .
, torus networks .
, regular graphs .
, block graphs .
, bouquet graphs .
, and split graphs .
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 .
Meanwhile.
RodrAguezVelaAzquez et al.
studied the parameter for corona product graphs .
and rooted product graphs .
The lower and upper bounds on the local metric dimension of the generalized hierarchical product are proved in .
BarragaAn-RamArez et al.
determined the local metric dimension of lexicographic product graphs .
and strong product graphs .
Now, for n OO N and i OO .
, 2, .
, .
, let us consider a simple connected graph Hi 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 Oe 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 Oe Amal{H.
J} for J is either K1 or P2 .
The local metric dimension of amalgamation of graphs Fitriani and S.
Saputro Subgraph Amalgamation For n OO N and i OO .
, 2, .
, .
, let Hi be a simple connected graph of order ki Ou 2 containing a connected subgraph J of order p where 1 O p < ki .
Let V (Hi ) = .
1 , h2 , .
, hp , hp 1 , .
, hki } where V (J) = .
1 , h2 , .
, hp }.
Now, let us consider H = {H1 .
H2 , .
Hn }.
In this section, we denote H O = Subgraph Oe Amal{H.
J}.
We define V (H) = V (J) O .
O i O n, p 1 O j O ki } and Hi? = V (J) O .
1 O j O ki }.
Figure 1.
Subgraph amalgamation of H1 .
H2 , .
Hn In Lemma 2.
1 below, we prove that every graph G OO H contibutes at least lmd(G) Oe p vertices in a local basis of H.
Meanwhile in Lemma 2.
2, we provide a local resolving set of subgraphamalgamation H, which is union of local basis of every graph in H.
Lemma 2.
Let W be a local basis of H O = Subgraph Oe Amal{H.
J}.
Then every graph G OO H contibutes at least lmd(G) Oe p vertices in W .
Proof.
Suppose that there exists i OO .
, 2, .
, .
such that Hi contributes at most lmd(Hi )OepOe1 vertices in W .
Let Wi = W O V (Hi ) and Si = .
t | h.
, .
OO Wi }.
Now, we define Ai = Si O V (J).
Note that |Ai | < lmd(Hi ).
Since all vertices of J are in Ai , so there exist two adjacent vertices hk and hl in V (Hi ) \ V (J) satisfying r.
k | A) = r.
l | A), which implies r.
| Wi ) = r.
| Wi ).
Since every vertex z OO V (H) \ V (Hi ) and u OO V (Hi ) \ V (J) satisfies dH .
, .
= dH .
, .
dH .
, .
for some v OO V (J), it follows that r.
| W ) = r.
| W ), a contradiction.
Lemma 2.
Let Bi be a local basis of Hi .
Then W = ni=1 Bi be a local resolving set of H O Subgraph Oe Amal{H.
J}.
Proof.
Let us consider an edge xy OO E(H).
Then there exists i OO .
, 2, .
, .
such that x, y OO V (Hi ).
Since every S two adjacent vertices in Hi are locally resolved by some vertices of Bi , we obtain that W = ni=1 Bi is a local resolving set of H.
The local metric dimension of amalgamation of graphs Fitriani and S.
Saputro 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.
For n Ou 2 and i OO .
, 2, .
, .
, let Hi be a simple connected graph containing a connected subgraph J and H = {H1 .
H2 , .
Hn }.
Let |V (J)| = p.
Then lmd(Hi ) Oe pn O lmd(Subgraph Oe Amal{H.
J}) O
lmd(Hi ).
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.
Theorem 2.
For n Ou 2 and i OO .
, 2, .
, .
, let Hi be a simple connected graph containing a connected subgraph J and H = {H1 .
H2 , .
Hn }.
If every local basis of Hi .
O i O .
does not contain all vertices of J and every in J is adjacent to every vertex in V (Hi ) \ V (J), then Pvertex lmd(Subgraph Oe Amal{H.
J}) = i=1 lmd(Hi ).
Proof.
By Theorem 2.
1, we only Pnneed to show that lmd(H) Ou i=1 lmd(Hi ).
Suppose that lmd(H) O ( i=1 lmd(Hi )) Oe 1 and W be a local basis of H.
Let Bi be a local basis of Hi .
Note that Bi does not contain all vertices of J.
Then there exists i OO .
, 2, .
, .
such that h.
OO / W where hl OO Bi .
Let Bi = Bi \ .
l }.
Since |Bi | < lmd(Hi ), there exist two adjacent vertices hs , ht in Hi satisfying r.
s | Bi ) = r.
t | Bi ).
Let B.
= .
| hk OO Bi }.
Thus, r.
| B.
) = r.
| B.
Since dH .
, hj ) = dH .
, hj ) for each h.
, h.
OO V (H) \ V (J) and j OO .
, 2, .
, .
, we obtain that r.
|W ) = r.
|W ), a contradiction.
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.
this theorem.
P we give a property of subgraph-amalgamation graph whose local metric dimension is equal to ni=1 lmd(Hi ) Oe cn where 0 < c O p.
If c = p, then we have a subgraph-amalgamation graph H where lmd(H) is equal to the lower bound in Theorem 2.
Theorem 2.
For n Ou 2 and i OO .
, 2, .
, .
, let Hi be a simple connected graph containing a connected subgraph J and H = {H1 .
H2 , .
Hn }.
Let |V (J)| = p Ou 1 and V (J) = .
1 , h2 , .
, hp }.
Let C be a non-empty subset of V (J) where C = .
1 , h2 , .
, hc }.
Let lmd(Hi ) Ou 2c and every local basis Bi of Hi contains x OO V (J) if and only if x OO C.
If there exists a subset .
p 1 , hp 2 , .
, hp c } of Bi \ C such that dHi .
j , hp j )P< dHi .
k , hp j ) for every distinct j, k OO .
, 2, .
, .
, then lmd(Subgraph Oe Amal{H.
J}) = ni=1 lmd(Hi ) Oe cn.
Proof.
Suppose that W is a local basis of H satisfying |W | = lmd(H) O ( ni=1 lmd(Hi )Oec.
Oe1.
Then there exists i OO .
, 2, .
, .
such that Hi contributes at most lmd(Hi ) Oe c Oe 1 vertices in W .
Let Si = W O V (Hi ) and Wi = .
j OO V (Hi ) | h.
OO Si }, then |Wi | O lmd(Hi ) Oe c Oe 1.
Let A OI C where every element of A, say hb , locally resolves some two adjacent vertices in Hi? and there exists v OO W \ Hi? which satisfies dH .
, hb ) = min.
H .
, .
| w OO C}.
Since every local basis Bi of Hi does not contain all vertices of V (J) \ C and |Wi O A| < |Bi |, there exist two adjacent vertices hk , hl in Hi which are not locally resolved by vertices in Wi O A, which implies The local metric dimension of amalgamation of graphs Fitriani and S.
Saputro h.
, h.
are not locally resolved by vertices in Si O A.
It follows that h.
, h.
are not locally resolved by W , a contradiction.
For i OO .
, 2, .
, .
, let Ti = Bi \ C.
We define Ui = .
| hl OO Ti } and W = ni=1 Ui .
will show that W is a local resolving set of H.
We consider any two adjacent vertices h.
, h.
OO V (H) \ W in two following cases.
A There exist hs , ht in Hi which are locally resolved by Wi .
Let hl OO Ti locally resolves hs and ht .
Then it is clear that h.
, h.
in H will be locally resolved by h.
OO W .
A Every two adjacent vertices hs , ht in Hi are not locally resolved by Wi .
Then there exists hj OO C such that dHi .
s , hj ) 6= dHi .
t , hj ).
Therefore, we have dH .
, hj ) 6= dH .
, hj ).
We consider h.
,p .
OO W where m OO .
, 2, .
, .
and dHi .
j , h.
) < dHi .
k , h.
) for every distinct j, k OO .
, 2, .
, .
We obtain dH .
, h.
,p .
) = dH .
, hj ) dH .
j , h.
,p .
) = dH .
, hj ) dHi .
j , hp j ) 6= dH .
, hj ) dHi .
j , hp j ) = dH .
, hj ) dH .
, h.
,p .
) = dH .
, h.
,p .
Then h.
, h.
in H are locally resolved by h.
,p .
OO W.
Therefore.
W is a local resolving set of H.
Note that, in Theorem 2.
3 above, we consider a graph Subgraph Oe Amal{H.
J} where every local basis of Hi OO H .
O i O .
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.
Theorem 2.
For n Ou 2 and i OO .
, 2, .
, .
, let Hi be a simple connected graph containing a connected subgraph J and H = {H1 .
H2 , .
Hn }.
Let |V (J)| = p Ou 1 and C be a non-empty subset of V (J) where |C| = c.
Let every local basis Bi of Hi contains x OO V (J) if and only if x OO C.
Then lmd(Subgraph Oe Amal{H.
J}) O
lmd(Hi ) Oe cn c.
Proof.
Let us consider any edges xy OO E(H).
Then there exists i OO .
, 2, .
, .
such that x, y OO V (Hi ).
For i OO .
, 2, .
, .
, let Bi be a local basis of Hi .
SinceS every two adjacent vertices in Hi are locally resolved by some vertices in Bi , we obtain that W = ni=1 BP i is a local resolving set of H.
Since |Bi OBj | = c for distinct i, j OO .
, 2, .
, .
, we have |W | = ni=1 |Bi |Oe.
Oe.
Therefore, we obtain lmd(H) O lmd(Hi ) Oe cn c.
The local metric dimension of amalgamation of graphs Fitriani and S.
Saputro 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 G1 and its complement are shown in Figure 2.
Figure 2.
Graph G1 .
and its complement .
Lemma 2.
Let G1 be a connected graph as stated in Figure 2.
Then lmd(G1 ) = 3.
Moreover, the set .
1 , f2 , f3 } is the only local basis of G1 .
Proof.
Let D = .
i | i OO .
, 2, .
E = .
i | i OO .
, 2, .
F = .
i | i OO .
, 2, .
}, and G = .
i | i OO .
, 2, .
Since G1 contains an odd cycle, we have lmd(G1 ) > 1.
We will show that there is no local resolving set of G1 whose cardinality is 2.
Suppose that W be a local resolving set of G1 with |W | = 2.
We distinguish four cases.
Case 1.
W OC D O F
Since |W | = 2, there exists i OO .
, 2, .
such that fi OO / W .
So, we obtain that r.
i | W ) = .
, .
= r.
i | W ).
Case 2.
W OC D O E O G
Then D \ W 6= OI and E \ W 6= OI.
Let di , ej OO / W .
Note that di and ej are adjacent.
So, we obtain that r.
i | W ) = .
, .
= r.
j | W ).
Case 3.
W = .
i , fj } where i, j OO .
, 2, .
Then two adjacent vertices fk , gl satisfy r.
k | W ) = .
, .
= r.
l | W ) with k, l OO .
, 2, .
and k 6= i, l 6= j.
Case 4.
W = .
i , gj } where i, j OO .
, 2, .
Then two adjacent vertices ek , el satisfy r.
k | W ) = .
, .
= r.
l | W ) with k, l OO .
, 2, .
\ .
The local metric dimension of amalgamation of graphs Fitriani and S.
Saputro 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 G1 with 2 elements, we obtain that lmd(G1 ) Ou 3.
Now, we will construct a local resolving set of G1 with 3 vertices.
Define B = .
1 , f2 , f3 }.
The representation of all vertices in G1 with respect to B are as follows.
1 |B) = .
, 2, .
2 |B) = .
, 1, .
3 |B) = .
, 2, .
1 |B) = .
, 1, .
2 |B) = .
, 2, .
3 |B) = .
, 1, .
1 |B) = .
, 1, .
2 |B) = .
, 0, .
3 |B) = .
, 1, .
1 |B) = .
, 1, .
2 |B) = .
, 1, .
3 |B) = .
, 1, .
Since there are no two adjacent vertices of G1 having the same representation, we obtain that B is a local resolving set of G1 , which implies lmd(G1 ) O 3.
Next, we will show that there is no local resolving set of G1 with 3 vertices, except .
1 , f2 , f3 }.
Let W 0 OC V (G1 ) with |W 0 | = 3 and W 0 contains q vertices in F with 0 O q O 2.
We distinguish three cases.
Case 1.
q = 0
A W0 O G = OI
If W 0 = E, then two adjacent vertices d OO D and g OO G satisfy r.
| W 0 ) = .
, 1, .
= r.
| W 0 ).
Otherwise, let ei OO / W .
OO .
, 2, .
Then we obtain r.
i | W 0 ) = .
, 1, .
= r.
i | W ).
A W 0 O G 6= OI
Then there exist d OO D and e OO E which are not element of W 0 .
Then we obtain r.
| W 0 ) = .
, 1, .
= r.
| W 0 ).
Case 2.
q = 1
A W0 O G = OI
If W 0 O D = OI, then two adjacent vertices d OO D and g OO G satisfy r.
| W 0 ) = .
, 1, .
= r.
| W 0 ).
Otherwise, let ei OO / W .
OO .
, 2, .
Then we obtain r.
i | W 0 ) = .
, 1, .
= r.
i | W 0 ).
A W 0 O G 6= OI
If W 0 O E = OI, then there exist two distinct vertices of E which are adjacent to W 0 .
Otherwise, all three vertices of D are adjacent to W 0 .
Case 3.
q = 2 Let two distinct vertices fj , fk OO W 0 where j, k OO .
, 2, .
A W 0 O D 6= OI
Then for l OO .
, 2, .
\ .
, .
, we have el is adjacent to W 0 .
So, for g OO G, we obtain r.
l | W 0 ) = .
, 1, .
= r.
| W 0 ).
The local metric dimension of amalgamation of graphs Fitriani and S.
Saputro
A W 0 O G 6= OI
Then two adjacent vertices dj , ek satisfy r.
j | W 0 ) = r.
k | W 0 ).
A W 0 O E 6= OI
Let ei OO W 0 .
If i = j, then two adjacent vertices dj , ek satisfy r.
j | W 0 ) = r.
k | W 0 ).
Otherwise, two adjacent vertices dk , ej satisfy r.
k | W 0 ) = r.
j | W 0 ).
By all cases above.
W 0 is not local resolving set of G1 .
Now, we are ready to give an existence of H = {H1 .
H2 , .
Hn } and a terminal subgraph J of Hi , such that the local metric dimension of Subgraph Oe Amal{H.
J} is equal to the upper bound of Theorem 2.
Theorem 2.
For n Ou 2 and i OO .
, 2, .
, .
, let Hi O = G1 .
J be a terminal subgraph of Hi with V (J) = .
1 , f2 , e3 }, and H = {H1 .
H2 , .
Hn }.
Then lmd(Subgraph Oe Amal{H.
J}) = n 2.
Proof.
In this case.
C = .
1 , f2 } and c = |C| = 2.
ByPTheorem 2.
4, lmd(H) O ni=1 lmd(Hi ) Oe cn c = n 2.
Now, we will prove that lmd(H) Ou ni=1 lmd(Hi ) Oe cn c = n 2.
Let x.
OO V (H) \ V (J) whenever xj OO V (Hi ) \ V (J) and W be a local resolving set of H.
We consider two conditions below.
Two adjacent vertices d1 and e2 are not locally resolved by J.
It follows that d.
and e.
in H are not locally resolved by V (H) \ Hi? .
Since f3 is an element of local basis of G1 and f3 locally resolves d1 and e2 , we obtain that f.
locally resolves d.
and e.
Thus, f.
OO W for 1 O i O n.
For j OO .
, .
, two adjacent vertices ej and gj are not locally resolved by J \.
j }.
According to Lemma 2.
3, fj is an element of a local basis of G1 .
Note that if fj 6OO W , then e.
and g.
are not locally resolved by V (H) \ Hi? since dH .
, e.
) < dH .
, fj ) dH .
j , e.
) and dH .
, g.
) = dH .
, fj ) dH .
j , g.
) with v OO V (H) \ Hi? .
So, fj must be in W for j OO .
, .
By two conditions above, we obtain that lmd(H) Ou n 2.
In the next theorem, we will provide an existence of H = {H1 .
H2 , .
Hn } and a terminal subgraph J of Hi , such that the local metric dimension of Subgraph Oe Amal{H.
J} is not equal to both upper bound of Theorem 2.
4 and lower bound of Theorem 2.
In order to do so, first, we need to determine the local metric dimension of graph G2 , which can be seen in Lemma 2.
4 below.
The lemma is proved by using the similar argument of Lemma 2.
Meanwhile, the graph G2 and its complement are shown in Figure 2.
Note that, the graph G2 can be obtained from G1 by adding an edge f1 f3 .
Lemma 2.
Let G2 be a connected graph as stated in Figure 3.
Then lmd(G2 ) = 3.
Moreover, the set .
1 , f2 , f3 } is the only local basis of G2 .
Theorem 2.
For n Ou 2 and i OO .
, 2, .
, .
, let Hi O = G2 .
J be a terminal subgraph of Hi with V (J) = .
1 , f2 , e3 }, and H = {H1 .
H2 , .
Hn }.
Then lmd(Subgraph Oe Amal{H.
J}) = n 1.
The local metric dimension of amalgamation of graphs Fitriani and S.
Saputro Figure 3.
Graph G2 .
and its complement .
Proof.
Pn In this case.
C = .
1 , f2 } and c = |C| = 2.
Note that, i=1 lmd(Hi ) Oe cn = n < n 1 < i=1 lmd(Hi ) Oe cn c = n 2.
Now, we will prove that lmd(H) Ou n 1.
Let x.
OO V (H) \ V (J) whenever xj OO V (Hi ) \ V (J) and W be a local resolving set of H.
We consider two conditions below.
Two adjacent vertices d1 and e2 are not locally resolved by J.
It follows that d.
and e.
in H are not locally resolved by V (H) \ Hi? .
Since f3 is an element of local basis of G2 and f3 locally resolves d1 and e2 , we obtain that f.
locally resolves d.
and e.
Thus, it must be f.
OO W for 1 O i O n.
Two adjacent vertices e1 and g1 are not locally resolved by J \ .
1 }.
According to Lemma 2, f1 is an element of a local basis of G2 .
Note that, if f1 6OO W , then e.
and g.
are not locally resolved by V (H) \ Hi? since dH .
, e.
) < dH .
, f1 ) dH .
1 , e.
) and dH .
, g.
) = dH .
, f1 ) dH .
1 , g.
) with v OO V (H) \ Hi? .
So, f1 must be in W.
By two conditions above, we obtain that lmd(H) Ou n 1.
Now, we will construct a local resolving set of H with n 1 vertices.
Define B = .
1 }O.
| 1 O i O .
The representation of all vertices in H with respect to B are as follows.
The local metric dimension of amalgamation of graphs r.
1 | B) = .
, 2, .
, .
2 | B) = .
, 1, .
, .
3 | B) = .
, 2, .
, .
| B) = .
, 2, 3, .
, .
| B) = .
, 2, 2, .
, .
| B) = .
, 1, 3, .
, .
| B) = .
, 1, 2, .
, .
| B) = .
, 1, 3, .
, .
| B) = .
, 0, 2, .
, .
| B) = .
, 1, 2, .
, .
| B) = .
, 1, 2, .
, .
| B) = .
, 1, 2, .
, .
| B) = .
, 3, 2, 3, .
, .
| B) = .
, 2, 2, 2, .
, .
| B) = .
, 3, 1, 3, .
, .
Fitriani and S.
Saputro r.
| B) = .
, 2, 1, 2, .
, .
| B) = .
, 3, 1, 3, .
, .
| B) = .
, 2, 0, 2, .
, .
| B) = .
, 2, 1, 2, .
, .
| B) = .
, 2, 1, 2, .
, .
| B) = .
, 2, 1, 2, .
, .
| B) = .
, 3, 3, .
, 3, 2, 3, .
, .
| B) = .
, 2, 2, .
, 2, 2, 2, .
, .
| B) = .
, 3, 3, .
, 3, 1, 3, .
, .
| B) = .
, 2, 2, .
, 2, 1, 2, .
, .
| B) = .
, 3, 3, .
, 3, 1, 3, .
, .
| B) = .
, 2, 2, .
, 2, 0, 2, .
, .
| B) = .
, 2, 2, .
, 2, 1, 2, .
, .
| B) = .
, 2, 2, .
, 2, 1, 2, .
, .
| B) = .
, 2, 2, .
, 2, 1, 2, .
, .
where k OO .
, 4, .
, .
and dH .
, f.
) = dG2 .
l , f3 ) for each vl OO D O E O F O 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) O n 1.
Vertex Amalgamation For n OO N and i OO .
, 2, .
, .
, let Hi be a simple connected graph of order ki Ou 2 containing a connected subgraph J of order p where 1 O p < ki .
In this section, let H = {H1 .
H2 , .
Hn } where J only consists of one vertex.
The graph SubgraphOeAmal{H.
J} then is called as a vertex amalgamation graph.
Let V (Hi ) = .
, h2 , .
, hki } where V (J) = .
In this section, we denote H O = SubgraphOe Amal{H.
J}.
We define V (H) = .
O .
O i O n, 2 O j O ki }.
= .
O j O ki }, and Hi? = .
O H.
We also define:
A S = {A OO H | A is not bipartite and there exists a local basis of A containing .
A T = {A OO H | A is not bipartite and every local basis of A does not contain .
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.
For s t Ou 1, there exist two adjacent vertices h.
and h.
satisfying dH .
, .
= dH .
, .
where i OO .
, 2, .
, s .
and j, k OO .
, 3, .
, ki }.
Proof.
Since s t Ou 1, for i OO .
, 2, .
, s .
, we have Hi is not bipartite and contains an odd cycle C.
We distinguish two cases.
Case 1.
h OO V (C) Then there exist two adjacent vertices hj , hk OO V (C) \ .
satisfying dHi .
j , .
= dHi .
k , .
The local metric dimension of amalgamation of graphs Fitriani and S.
Saputro obtain that dH .
, .
= dH .
, .
Case 2.
h OO
/ V (C)
Let hl OO V (C) such that dHi .
l , .
= min.
Hi .
, .
OO V (C)}.
Then there exist two adjacent vertices hj , hk OO V (C) \ .
l } satisfying dHi .
j , hl ) = dHi .
k , hl ) and dHi .
j , .
= dHi .
j , hl ) dHi .
l , .
= dHi .
k , hl ) dHi .
l , .
= dHi .
k , .
Therefore, we obtain that dH .
, .
= dH .
, .
In the next two lemmas, we provide some properties of local basis of the vertex amalgamation graph H.
Lemma 3.
Let W be a local basis of H.
If s t Ou 1, then .
W O H.
6= OI for every i OO .
, 2, .
, s .
W O H.
= OI for every j OO .
t 1, s t 2, .
, .
Proof.
We distinguish two cases of proof.
W O H.
6= OI for every i OO .
, 2, .
, s .
Suppose that W O H.
= OI for some i OO .
, 2, .
, s .
Let w OO W .
Note that w OO H.
By Proposition 3.
1, there exist two adjacent vertices h.
and h.
in H satisfying dH .
, .
= dH .
, .
So, we have dH .
, .
= dH .
, .
dH .
, .
= dH .
, .
dH .
, .
= dH .
, .
Therefore, we obtain r.
| W ) = r.
| W ), a contradiction.
W O H.
= OI for every j OO .
t 1, s t 2, .
, .
Suppose that there exists j OO .
t 1, s t 2, .
, .
such that W O H.
6= OI.
Let w OO H.
be an element of W .
We consider W 0 = W \ .
We will show that W 0 is still a local resolving set of H.
By considering .
, let S = .
OO W | x OO H.
, 1 O i O s .
Note that, by the definition of W 0 , we also have that S OI W 0 .
Let x, y be two adjacent vertices in V (H) \ W 0 .
So, there exists i OO .
, 2, .
, .
such that x, y OO Hi? .
We distinguish two cases.
Case 1.
i OO .
, 2, .
, s .
By .
, we have that x, y are locally resolved by vertices in S.
It follows that both vertices are locally resolved by W 0 .
The local metric dimension of amalgamation of graphs Fitriani and S.
Saputro Case 2.
i OO .
t 1, s t 2, .
, .
Since every Hi with i OO .
t 1, s t 2, .
, .
is bipartite, we have lmd(Hi ) = 1.
Let Bi be a local basis of Hi .
Then for every v OO V (Hi ), there exists Bi where Bi = .
Thus, dHi .
0 , .
6= dHi .
0 , .
for every two adjacent vertices x0 , y 0 OO V (Hi ) \ .
Let v = h, we obtain that dHi .
0 , .
6= dHi .
0 , .
Consider two vertices x, y OO Hi? which are corresponded to x0 , y 0 OO V (Hi ) \ .
, respectively.
For any z OO W 0 , we obtain that dH .
, .
= dH .
, .
dH .
, .
= dHi .
0 , .
dH .
, .
6= dHi .
0 , .
dH .
, .
= dH .
, .
dH .
, .
= dH .
, .
So, r.
W 0 ) 6= r.
W 0 ).
Then every two adjacent vertices x, y OO V (H) \ W 0 are locally resolved by vertices in W 0 .
In both cases, we obtain that W 0 is a local resolving set of H, a Lemma 3.
Let W be a local basis of H.
If s > 1 or t Ou 1, then h 6OO W .
Proof.
Let W be a local basis of H where h OO W .
We consider W 0 = W \ .
We will show that W 0 is also a local resolving set of H.
Let x and y be two adjacent vertices in V (H) \ W 0 .
By considering properties in Lemma 3.
we have that x and y are locally resolved by vertices in W 0 .
Thus, we have a contradiction.
From proposition and lemmas above we have the following theorem.
Theorem 3.
For n Ou 2 and i OO .
, 2, .
, .
, let Hi be a simple connected graph of order at least 2 containing a subgraph J and H = {H1 .
H2 , .
Hn }.
Let J = K1 where V (J) = .
Let S = {A OO H | A is not bipartite and there exists a local basis of A containing .
and T = {A OO H | A is not bipartite and every local basis of A does not contain .
If s = |S|, t = |T | and the first s t elements in H are from S O T , then s = t = 0.
lmd(Hs ), s = 1 and t = 0.
lmd(Subgraph Oe Amal{H.
J}) =
Ps t i=1 lmd(Hi ) Oe s, s Ou 2 or t Ou 1.
Proof.
Let H O = Subgraph Oe Amal{H.
J}.
If s = t = 0, then every graph Hi is bipartite.
It follows that H is also bipartite.
Okamoto et al.
have been proved that the local metric dimension of any bipartite graphs is 1.
Now, assume s Ou 1 or t Ou 1.
Let 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 }.
We have two cases.
The local metric dimension of amalgamation of graphs Fitriani and S.
Saputro Case 1.
s = 1 and t = 0.
First, we will show that lmd(H) O lmd(Hs ) by constructing a local resolving set with lmd(Hs ) Let Bs be a local basis of Hs containing h.
We define Bs = Bs \ .
and W = .
| ht OO Bs } O .
Let us consider any two adjacent vertices h.
, h.
OO V (H) \ W .
If i = s = 1, then hj and hk are locally resolved by Bs , which implies h.
, h.
are locally resolved by W .
Now, we assume that i OO .
, 3, .
, .
We obtain that Hi is a bipartite graph.
Since there exists a local basis of Hi containing exactly one vertex h, then h.
, h.
of H are locally resolved by h OO W.
Thus.
W is a local resolving set of H.
Next, we will show that lmd(H) Ou lmd(Hs ).
Suppose that lmd(H) O .
md(Hs )) Oe 1.
Let S be a local basis of H.
So, |S| O lmd(Hs ) Oe 1.
By Lemma 3.
S O Hi = OI, i OO .
, 3, .
, .
We define a subset U of V (Hs ) as .
O .
j | h.
OO S}.
Since |U | = |S| O lmd(Hs ) Oe 1, there exist two adjacent vertices hk , hl OO V (Hs ) satisfying r.
k | U ) = r.
l | U ).
It follows that r.
| S) = r.
| S), a contradiction.
Case 2.
s Ou 2 or t Ou 1.
Ps t First, lmd(H) O i=1 lmd(Hi ) Oe s by constructing a local resolving set with Ps t i=1 lmd(Hi ) Oe s vertices.
Since s Ou 2 or t Ou 1 for i OO .
, 2, .
, s .
Hi is not bipartite and lmd(Hi ) > 1.
A s Ou 1 and i OO .
, 2, .
, .
Let Bi be a local basis of Hi containing h.
Then we define Wi = .
j OO Bi \ .
A t Ou 1 and i OO .
1, s 2, .
, s .
Let Ci be a local basis of Hi .
We define Wi = .
j OO Ci }.
Ss t Wi .
Note that W satisfies Lemmas 3.
1 and 3.
Let us consider any two Now, define W = i=1 adjacent vertices x, y OO V (H) \ W .
Note that there exists i OO .
, 2, .
, .
such that x, y OO Hi? .
A s 6= 0 and i OO .
, 2, .
, .
If dH .
, .
6= dH .
, .
, then it is clear that x, y are locally resolved by vertices in W \ Wi .
Otherwise, x, y are locally resolved by vertices in Wi .
A t 6= 0 and i OO .
1, s 2, .
, s .
Then x, y are locally resolved by vertices in Wi .
A s t < n and i OO .
t 1, s t 2, .
, .
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 P of H.
Next, suppose that lmd(H) O ( s t i=1 lmd(Hi ) Oe .
Oe 1.
Let W be a local basis of H.
Lemma 3.
and LemmaP3.
2, we have W O H.
= OI for every j OO .
t 1, s t 2, .
, .
and h 6OO W .
Since |W | O s t i=1 lmd(Hi ) Oe s Oe 1, we obtain two possibilities.
The local metric dimension of amalgamation of graphs Fitriani and S.
Saputro There exists i OO .
, 2, .
, .
such that |W O Hi? | O lmd(Hi ) Oe 2 Let Wi = W O Hi? and Si = .
j | h.
OO Wi } O .
Since |Si | < lmd(Hi ), then there exists two adjacent vertices hk , hl in Hi which are not locally resolved by Si .
It follows that h.
, h.
are not locally resolved by Wi , which implies r.
| W ) = r.
| W ).
There exists i OO .
1, s 2, .
, s .
such that |W O Hi? | O lmd(Hj ) Oe 1 Let Wi = W O Hi? and Si = .
j | h.
OO Wi } O .
Note that, |Si | = lmd(Hi ).
However, every local basis of Hi does not contain h.
It follows that Si is not a local resolving set of Hi .
Then there exists two adjacent vertices hk , hl in Hi which are not locally resolved by Si .
It follows that h.
, h.
are not locally resolved by Wi , which implies r.
| W ) = r.
| W ).
By both possibilities above, we have a contradiction.
Edge Amalgamation For n OO N and i OO .
, 2, .
, .
, let Hi be a simple connected graph of order ki Ou 2 containing a connected subgraph J of order p where 1 O p < ki .
In this section, let H = {H1 .
H2 , .
Hn } where J O = P2 .
Since P2 has only one edge, the graph Subgraph Oe Amal{H.
J} then is called as an edge amalgamation graph.
Let V (Hi ) = .
1 , h2 , .
, hki } where V (J) = .
1 , h2 }.
In this section, we denote H O Subgraph Oe Amal{H.
J}.
We define V (H) = .
1 , h2 } O .
O i O n, 3 O j O ki }.
= .
O j O ki }, and Hi? = .
1 , h2 } O H.
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.
For n Ou 2 and i OO .
, 2, .
, .
, let Hi be a simple connected graph of order at least 3 and H = {H1 .
H2 , .
Hn }.
Then lmd(Hi ) Oe 2n O lmd(Subgraph Oe Amal{H.
P2 }) O
lmd(Hi ).
In this section, we will show that all values between the lower and upper bound in Theorem 4.
are achievable.
In order to do so, we need to determine the local metric dimension of graphs G3 .
G4 , and G5 .
The graph G3 and its complement are illustrated in Figures 4.
Meanwhile the graphs G4 and G5 can be seen in Figures 5 and 6, respectively.
First, let us consider the graph G3 .
Let N3 = .
1 , a2 }.
O3 = .
3 , a4 }.
P3 = .
5 , a6 }.
R3 = .
7 , a8 }, and S3 = .
9 , a10 , a11 , a12 }.
Now, we are ready to determine the local metric dimension of G3 .
Lemma 4.
Let G3 be a connected graph as stated in Figure 4.
Then lmd(G3 ) = 4.
Moreover the set .
1 , a2 , a7 , a8 } is a local basis of G3 .
Proof.
Since G3 contains an odd cycle, we have lmd(G3 ) > 1.
Next, we will show that there is no local resolving set of G3 with 2 elements.
Suppose that W be a local resolving set of G3 with The local metric dimension of amalgamation of graphs Fitriani and S.
Saputro Figure 4.
Graph G3 .
and its complement .
|W | = 2.
We obtain two cases.
Case 1.
W O S3 = OI.
Then there exist two distinct vertices x, y OO O3 O P3 which are adjacent to both vertices in W .
Therefore, we have r.
| W ) = .
, .
= r.
| W ).
Case 2.
W O S3 6= OI.
Let W = .
, .
where x OO S3 .
If y OO N3 O O3 , then we have r.
5 | W ) = .
, .
= r.
6 | W ).
Otherwise, we have r.
3 | W ) = .
, .
= r.
4 | W ).
By all cases above, we obtain that W is not local resolving set of G3 .
Therefore, we can conclude that lmd(G3 ) Ou 3.
However, we will also show that there is no local resolving set of G3 with cardinality 3.
Suppose that W 0 be a local resolving set of G3 with |W 0 | = 3.
Note that, at least one vertices of S3 are not in W 0 .
Without loss of generality, let a9 OO / W 0 .
Let |W 0 O S3 | = j where j OO .
, 1, 2, .
Then there exist j 1 vertices z1 , .
, zj 1 OO O3 O P3 which are adjacent to every vertex in W 0 .
If j = 0, we have r.
1 | W 0 ) = .
, .
= r.
9 | W 0 ).
Otherwise, r.
1 | W 0 ) = .
, .
= r.
2 | W 0 ).
Thus.
W 0 is not local resolving set of G3 .
Since there is no local resolving set of G3 with cardinality 3, we obtain that lmd(G3 ) Ou 4.
Next, we will show that lmd(G3 ) O 4.
Define W Ay = .
1 , a2 , a7 , a8 }.
The representation of all vertices in G3 with respect to W Ay are as follows.
1 |W A.
= .
, 1, 2, .
2 |W A.
= .
, 0, 1, .
7 |W A.
= .
, 1, 0, .
8 |W A.
= .
, 2, 1, .
3 |W A.
= .
, 1, 1, .
4 |W A.
= .
, 2, 1, .
5 |W A.
= .
, 1, 1, .
6 |W A.
= .
, 1, 2, .
9 |W A.
= .
, 1, 1, .
10 |W A.
= .
, 1, 1, .
11 |W A.
= .
, 1, 1, .
12 |W A.
= .
, 1, 1, .
Since there are no two adjacent vertices of G3 having the same representation, we conclude that The local metric dimension of amalgamation of graphs Fitriani and S.
Saputro W Ay is a local resolving set of G3 .
Figure 5.
Graph G4 Next, let us consider the graph G4 .
Let N4 = .
1 , b2 , b3 }.
O4 = .
i | 1 O i O t, t Ou .
P4 = .
1 , d2 , d3 }.
Now, we are ready to determine the local metric dimension of G4 .
Lemma 4.
Let G4 be a connected graph as stated in Figure 5.
Then lmd(G4 ) = 4.
Moreover, every local resolving set of G4 contains at least two vertices of N4 and at least two vertices of P4 .
Proof.
Let W be a local resolving set of G4 .
If |W O N4 | O 1 .
r |W O P4 | O .
, then there exist two distinct vertices x, y OO N4 .
r x, y OO P4 ) which are not element of W .
Since x and y are adjacent, and for every z OO V (G4 ) \ .
, .
, dG4 .
, .
= dG4 .
, .
, we have r.
| W ) = r.
| W ), a contradiction.
So, it must be |W O N4 | Ou 2 and |W O P4 | Ou 2, which implies lmd(G4 ) Ou 4.
Next, we will show that lmd(G4 ) O 4.
Define W 0 = .
1 , b2 , d1 , d2 }.
Let us consider two adjacent vertices u, v OO V (G4 ) \ W 0 .
If dG4 .
, b1 ) 6= dG4 .
, b1 ), then we obtain r.
| W 0 ) 6= r.
| W 0 ).
Otherwise, we have u = b3 and v = c1 .
Since dG4 .
, d1 ) = dG4 .
, d1 ) 1, we also obtain r.
| W 0 ) 6= r.
| W 0 ).
Thus.
W 0 is a local resolving set of G4 .
Figure 6.
Graph G5 The local metric dimension of amalgamation of graphs Fitriani and S.
Saputro Lemma 4.
Let G5 be a connected graph as stated in Figure 6.
Then lmd(G5 ) = 2 where .
5 , e6 } is a local basis of G5 .
If a local resolving set B of G5 contains e1 or e2 , then |B| Ou 3.
Moreover, the set .
1 , e2 , e3 } is a local resolving set of G5 .
Proof.
Since G5 contains an odd cylce, we have lmd(G5 ) > 1.
Next, we will construct a local resolving set of G5 with 2 vertices.
Define W = .
5 , e6 }.
The representation of all vertices in G5 with respect to W are as follows.
1 |W ) = .
, .
2 |W ) = .
, .
3 |W ) = .
, .
4 |W ) = .
, .
5 |W ) = .
, .
6 |W ) = .
, .
7 |W ) = .
, .
8 |W ) = .
, .
Since there are no two adjacent vertices having the same representation, we conclude that W is a local resolving set of G5 .
Next, we will show that every local basis B of G5 satisfies ei OO / B for i OO .
, .
Suppose that e1 OO B or e2 OO B.
If e1 , e2 OO B, then two adjacent vertices e3 and e8 are not locally resolved by B, a contradiction.
Now, we assume that either e1 OO B or e2 OO B.
For i OO .
, .
and j OO .
, .
\ .
, let ei OO B and ej OO / B.
Let D = .
3 , e4 , e4 i }.
If B O D 6= OI, then two adjacent vertices ej and e8 are not locally resolved by B.
Otherwise, two adjacent vertices ej and e3 are not locally resolved by B.
Thus, we have that B is not local resolving set of G5 .
Now, let S = .
1 , e2 , e3 }.
The representation of all vertices in G5 with respect to S are as r.
1 |S) = .
, 1, .
3 |S) = .
, 1, .
5 |S) = .
, 1, .
7 |S) = .
, 1, .
2 |S) = .
, 0, .
4 |S) = .
, 1, .
6 |S) = .
, 2, .
8 |S) = .
, 1, .
Since there are no two adjacent vertices having the same representation, we conclude that S is a local resolving set of G5 .
Now, we are ready to show that all values between the lower and upper bound in Theorem 4.
are achievable, which can be seen in theorem below.
Theorem 4.
For n Ou 2 and i OO .
, 2, .
, .
, there exist simple connected graph Hi of order at least 3 and H = P {H1 .
H2 , .
Hn } such thatP lmd(Subgraph Oe Amal{H.
P2 }) = k for every integer k satisfying i=1 lmd(Hi ) Oe 2n < k < ni=1 lmd(Hi ).
Proof.
Let us consider a finite collection H = {H1 .
H2 , .
Hn } where Hi = G3 .
Let a1 a2 be the edge from every Hi and H O = Subgraph Oe Amal{H.
P2 }.
We will show Pn that lmd(H) = i=1 lmd(Hi ) Oe 2n.
Sn By Theorem 2.
1, we only need to show that lmd(H) O i=1 lmd(Hi ) Oe 2n.
Define W = i=1 .
, a.
Let us consider any two adjacent vertices x1 , x2 OO V (H) \ W .
Then there exists i OO .
, 2, .
, .
such that x1 , x2 OO Hi? .
Let y1 , y2 OO V (Hi ) which are corresponded to x1 , x2 OO V (H), respectively.
It is clear that y1 is also adjacent to y2 in Hi .
If a7 or a8 is locally resolves y1 and y2 , then it follows that x1 and x2 are locally resolves by W .
Otherwise, y1 and y2 are locally resolved by a1 or a2 .
The local metric dimension of amalgamation of graphs Fitriani and S.
Saputro A y1 and y2 are locally resolved by a1 Then for l OO .
, 2, .
, .
\ .
, we have dH .
1 , a.
) = dH .
1 , a1 ) dH .
1 , a.
) = dHi .
1 , a1 ) dHi .
1 , a8 ) 6= dHi .
2 , a1 ) dHi .
1 , a8 ) = dH .
2 , a1 ) dH .
1 , a.
) = dH .
2 , a.
A y1 and y2 are locally resolved by a2 Then for l OO .
, 2, .
, .
\ .
, we have dH .
1 , a.
) = dH .
1 , a2 ) dH .
2 , a.
) = dHi .
1 , a2 ) dHi .
2 , a7 ) 6= dHi .
2 , a2 ) dHi .
2 , a7 ) = dH .
2 , a2 ) dH .
2 , a.
) = dH .
2 , a.
Therefore.
W is a local resolving set of H.
It implies that lmd(H) = ni=1 lmd(H Pi ) Oe 2n.
To obtain an edge amalgamation graph whose local metric dimension is k = ni=1 lmd(Hi ) Oe 2n q for 1 O q O 2n, we replace some Hi in H by G4 or G5 according to the parity of q.
For l OO .
, 2, .
, .
, we distinguish two cases.
Case 1.
q = 2l Let H0 = {H10 .
H20 , .
Hn0 } be a finite collection which is obtain from H by replacing l elements of H by G4 .
Choose the terminal edge ct ct 1 for G4 and a1 a2 for G3 .
Case 2.
q = 2l Oe 1 Let H0 = {H10 .
H20 , .
Hn0 } be a finite collection which is obtain from H by replacing l Oe 1 elements of H by G4 and an element of H by G5 .
Choose the terminal edge e1 e2 for G5 , ct ct 1 for G4 , and a1 a2 for G3 .
By Lemma 4.
1, the graph G3 has a local basis S3 containing a1 , a2 .
However, by Lemmas 4.
G4 and G5 do not have a local basis containing ct , ct 1 and e1 , e2 , respectively.
So, for G4 and G5 , we consider a minimum resolving set S4 and S5 , respectively, containing two vertices of their terminal edge.
Note that, |S4 | Ou lmd(G4 ) 2 and |S5 | Ou lmd(G5 ) 1.
Thus, by using the similar argument with the proof of Lemma 2.
1, the graphs G3 .
G4 , and G5 must contribute at least lmd(G3 )Oe2, lmd(G4 ), and lmd(G5 )Oe1 vertices to a resolving set of SubgraphOeAmal{H0 .
P2 }.
Now, we will construct a resolving set of Subgraph Oe Amal{H0 .
P2 } with ni=1 lmd(Hi ) Oe 2n q vertices.
Let B3 .
B4 , and B5 be the set of vertices in Subgraph Oe Amal{H0 .
P2 } which are corresponded to vertices a7 and a8 of G3 , vertices b1 , b2 , d1 , and d2 of G4 , and vertex e3 of The local metric dimension of amalgamation of graphs Fitriani and S.
Saputro G5 , respectively.
Then, define B = B3 O B4 O B5 .
Note that, for q is even, we have B5 = OI.
Let = Subgraph Oe Amal{H0 .
P2 }.
Let us consider any two adjacent vertices x1 , x2 OO V (H) \ B.
Then there exists i OO .
, 2, .
, .
such that x1 , x2 OO Hi0? .
Let Hi0 O = Gj where j OO .
, 4, .
x1 , x2 are resolved by Bj , then we are done.
Otherwise, x1 , x2 then are resolved by a vertex in terminal edge of Hi0 .
We distinguish two cases.
Case 1.
Hi0 O
= G3
Let y1 , y2 OO V (Hi0 ) which are corresponded to x1 , x2 OO V (H), respectively.
Then it is clear that a1 or a2 is locally resolves y1 and y2 .
Note that, in H, the vertex a1 of Hi0 can be identified by ct or ct 1 of Hr0 where Hr0 O = G4 .
So, x1 , x2 are locally resolved by vertices in B4 .
Case 2.
Hi0 O
= G5
Let y1 , y2 OO V (Hi0 ) which are corresponded to x1 , x2 OO V (H), respectively.
Then it is clear that e1 or e2 is locally resolves y1 and y2 .
Note that, in H, the vertex e1 of Hi0 can be identified by a1 or a2 of Hr0 where Hr0 O = G3 , or by ct or ct 1 of Hr0 where Hr0 O = G4 .
So, x1 , x2 are locally resolved by vertices in B3 or B4 .
Conclusion Let H = {H1 .
H2 , .
Hn } be a finite collection of simple connected graphs, where Hi is a graph containing a connected subgraph J.
In this paper, we consider the subgraph-amalgamation graphs Subgraph Oe Amal{H.
J}.
This graph is constructed by taking all elements of H, then identifying all of them on J.
We provide the lower and upper bounds of lmd(Subgraph Oe Amal{H.
J}) for any structures of J.
These bounds are functions of lmd(Hi ) .
O i O .
We also provide some properties of Subgraph Oe Amal{H.
J} whose local metric dimension is equal to some values, including the upper and lower bound values.
Furthermore, we consider SubgraphOeAmal{H.
J} for certain structure of J.
For J is a vertex (J = K1 ), we determine an exact value of the local metric dimension of SubgraphOeAmal{H.
J}.
In case J is an edge (J = P2 ), we provide the lower and upper bounds of lmd(Subgraph Oe Amal{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 achievalbe if the order of J is at least 3.
The problem is stated as Problem 1.
Let J be a connected graph of order p Ou 3.
Does there exist H = {H P1n.
H2 , .
Hn } where Hi P is a connected graph containing J, such that for every integer t with i=1 lmd(Hi ) Oe pn < t < ni=1 lmd(Hi ), we have lmd(Subgraph Oe Amal{H.
J}) = t? Acknowledgement The authors are thankful to the anonymous referee for some comments that helped to improve the presentation of the manuscript.
The local metric dimension of amalgamation of graphs Fitriani and S.
Saputro
References