INTERNATIONAL JOURNAL OF COMPUTING SCIENCE AND APPLIED MATHEMATICS VOL.
NO.
MARCH 2024
Bi-Edge Metric Dimension of Graphs Rinurwati and Fadillah Dian Maharani AbstractAiGiven a connected G = (V (G).
E(G)) graph.
The main problem in graph metric dimensions is calculating the metric dimensions and their characterization.
In this research, a new dimension concept is introduced, namely a bi-edge metric dimension of graph which is a development of the concpet of bi-metric graphs with the innovation of bi-metric graph representations to become the bi-edge metric graph representations.
In this case, what is meant by bi-edge metric and edge detour.
If there is a set in G that causes every edge in G has a different bi-edge metric representation in G, then that set is called the biedge metric resolving set.
The minimum cardinality of the bi-edge metric resolving set graphs is called the bi-edge metric dimension of G graph, denoted by e dimb (G).
The spesific purpose of this research is to apply the concept of bi-edge metric dimensions to special graphs, such as cycle, complete, star and path can be Index TermsAiBi-Metric Dimension.
Edge Metric Dimension.
Edge Detour Dimension.
Bi-Edge Metric Dimension.
in the form of a k-vector of the pair of distances and detour between vertex u and v j , j OO N in the resolving set.
The concept of bi-metric dimension was recently introduced in .
, has only been implemented to obtain the bi-metric dimension of some special graphs, and for the resulting graph the bi-metric dimension has not yet been produced, and the development of the new bi-metric concept there is one .
, so not much research has been done.
Therefore, the bi-metric dimension has the potential to be further developed, both for the variant concept of bimetric dimension and for the bi-metric dimension of the resulting graph operation.
In this study a new variant of the bimetric dimension concept was developed which combines two dimension concepts called the bi-edge metric dimension graph, by developing a new method, namely a mixture of methods subgraph and pattern recognition.
I NTRODUCTION
II.
M AIN R ESULTS
HE metric dimension of an edge is a sub-field of research in graph theory where discussion has become lively starting when an articel was written in 2018 entitled Uniquely Identifying The Edge of a Graph: The Edge Metric Dimension.
In the article discussed about the edge resolving set.
set W is said to be an edge resolving set if each edge in G graph has a different edge representation of W .
The metric representation of an edge in G graph is measured based on the distance of that edge to the points in the resolving set.
The metric dimension of the edge is the minimum cardinality of the edge resolving set in G.
Research on edge metric dimensions is developed from two perspectives, namely from the concept and the graph, especially the graph of the result of operations.
The development of the metric dimension concept related to this research is the edge metric concept itself .
, the edge detour dimension concept and the bi-metric dimension.
In 2010, an article entitled On Edge Detour Graphs .
a new idea was raised, namely the edge detour dimension.
The development of the edge detour dimension is the determination of an edge detour representation of every edge e in G graph against the edge detour resolving set, which is in the form of a k-vector of the pair of the length of the longest path or detour between edge e and vertex v j , j OO N in the edge detour resolving set.
On the other hand, in 2014 there is an article entitled BiMetric Dimension of Graphs .
a new idea was raised too, namely the bi-metric dimension.
The development of this bimetric dimension is the determination of the representation of each vertex u in G graph against the resolving set, which is We start this section with the definition of the bi-edge metric dimension as follows.
Given a connected G graph with a set of vertices V (G) and a set of edges E(G).
An ordered set W = .
1 , w2 , .
, wk } OI V (G) is called a bi-edge metric resolving set of G if every edge in G has a different representation to W and e = xy, and x, y OO V (G).
The bi-edge metric representation of e OO E(G) with respect to W is a k-tuples.
Rinurwati and F.
Maharani are with the Department of Mathematics.
Institut Teknologi Sepuluh Nopember.
Surabaya, 60111 Indonesia e-mail:
rinur@matematika.
id, fdianm@gmail.
Manuscript received October 30, 2023.
accepted January 30, 2024.
W ) = (.
, w1 ), d.
, w2 ), .
, d.
, wk )), ( .
, w1 ), .
, w2 ), .
, .
, wk ))) where d.
, wi ) and .
, wi ) are the distance and detour between an edge e and a vertex wi , respectively, for i OO .
, 2, .
, .
A set W is called a bi-edge metric resolving set of G if every edge in G has different a bi-edge metric representation with respect to W .
The bi-edge metric resolving set that has minimal cardinality is called the bi-edge metric basis, while the number of vertices on the bi-edge metric basis is called the bi-edge metric dimension of G graph which is denoted by e dimb (G).
In the following is an example of obtaining the bi-edge metric dimension of an umbrella graph U6,5 consisting of a path of order six and a path of order five in Figure 1.
The graph in Figure 1 is an umbrella graph with a vertex set V (U6,5 ) = .
i , v j .
OO .
, 2, .
, .
, j OO .
, 2, .
, .
and an edge set E(U6,5 ) = .
OO .
, 2, .
, .
Select an ordered set W OI V (U6,5 ), with W = .
1 , u2 , u3 , u4 , u5 }, then the bi-edge metric representation is obtained as follows rbs .
1 |W ) = (.
, 0, 1, 2, .
, .
, 6, 6, 6, .
), rbs .
2 |W ) = (.
, 0, 0, 1, .
, .
, 6, 6, 6, .
), rbs .
3 |W ) = (.
, 1, 0, 0, .
, .
, 6, 6, 6, .
), rbs .
4 |W ) = (.
, 2, 1, 0, .
, .
, 6, 6, 6, .
), rbs .
5 |W ) = (.
, 2, 2, 1, .
, .
, 6, 6, 6, .
INTERNATIONAL JOURNAL OF COMPUTING SCIENCE AND APPLIED MATHEMATICS VOL.
NO.
MARCH 2024
ordered sets A.
B OI V (G).
If B ON A and B is not a bi-edge metric resolving set of G graph, then A is also not a bi-edge metric resolving set of G graph.
Proof.
It is known that B is not a bi-edge metric resolving set of G graph.
So for every edge in G has at least two edges that have the same bi-edge metric representation with respect to B.
Because B ON A, then AOB = .
1 , v2 , .
, vl }O.
1 , v2 , .
, vm } = .
1 , v2 , .
, vm } = B.
It is clear that for every edge in G has at least two edges that have the same bi-edge metric representation with respect to A.
So A is not a bi-edge metric resolving set of G graph n The main purpose of this research is to determine the exact values of a bi-edge metric dimension of Cn .
Kn .
Sn and Pn .
the following the theorem of a bi-edge metric dimension is Fig.
1: U6,5 Graph rbs .
6 |W ) = (.
, 1, 1, 1, .
, .
, 6, 6, 6, .
), rbs .
7 |W ) = (.
, 1, 1, 1, .
, .
, 6, 6, 6, .
), rbs .
8 |W ) = (.
, 1, 1, 0, .
, .
, 6, 6, 7, .
), rbs .
9 |W ) = (.
, 1, 0, 1, .
, .
, 6, 7, 6, .
), rbs .
10 |W ) = (.
, 0, 1, 1, .
, .
, 7, 6, 6, .
), rbs .
11 |W ) = (.
, 1, 1, 1, .
, .
, 6, 6, 6, .
), rbs .
12 |W ) = (.
, 1, 1, 1, .
, .
, 6, 5, 5, .
), rbs .
13 |W ) = (.
, 2, 2, 2, .
, .
, 7, 6, 6, .
), rbs .
14 |W ) = (.
, 3, 3, 3, .
, .
, 8, 7, 7, .
), rbs .
15 |W ) = (.
, 4, 4, 4, .
, .
, 9, 8, 8, .
Because every edge in U6,5 has different bi-edge metric representations with respect to W , then W is a bi-edge metric resolving set of U6,5 graph.
Furthermore, it is shown that W is a bi-edge metric resolving set with minimal cardinality.
Take any Q OI V (U6,5 ) with |Q| < |W | so |Q| = 4, then there are several cases that prove that Q is not a bi-edge metric resolving set of U6,5 graph.
It can be concluded that W is a bi-edge metric basis of U6,5 .
So, eb dim(U6,5 ) = 5.
n Below are several lemmas that can help in proving theorems relating to bi-edge metric dimension.
Lemma 1.
Let G be a connected graph with order n and two ordered sets A.
B OI V (G).
If A OI B and A is a bi-edge metric resolving set of G graph, then B is also a bi-edge metric resolving set of G graph.
Proof.
Suppose A = .
1 , v2 , .
, vl } and B = .
1 , v2 , .
, vm } with l O m O n.
It is known that A is a bi-edge metric resolving set of G graph.
An ordered set A is called a bi-edge metric resolving set of G graph if every edge in G has different bi-edge metric representations with respect to A.
Because A OI B, then AOB = .
1 , v2 , .
, vl }O.
1 , v2 , .
, vm } = .
1 , v2 , .
, vm } = B.
As a result, all edges in G have a different bi-edge metric representations with respect to B.
So B is a bi-edge metric resolving set of G graph.
n Lemma 2.
Let G be a connected graph with order n and two Theorem 3.
Let G be a cycle with order n Ou 3, then e dimb (G) = 2.
Proof.
Let V (G) = .
OO .
, 2, 3, .
, .
} with E(G) = .
i vi 1 .
OO .
, .
, n Oe .
} O .
n v1 }.
Let W = .
i , vi 1 .
OO .
, 2, .
, .
} OI V (G) with |W | = 2.
Without loss of generality, choose W = .
1 , v2 }, then there are two possible cases for n are presented below: .
n = 2k 1 and .
n = 2k with k OO N.
When n = 2k 1, k OO N, for every vi vi 1 , vn v1 OO E(G) with i OO .
, 2, .
, n Oe .
, applies:
i Oe 1, i OO 1, 2, .
, 2n n d.
i vi 1 , v1 ) = n Oe i, i OO 2 1, 2n 2, .
, n Oe 1 n v1 , v1 ) = 0 i Oe 1, i OO i vi 1 , v2 ) = i Oe 2, i OO 2, 3, .
, n2 1 n Oe i, i OO n 2, n 3, .
, n Oe 1 d.
n v1 , v2 ) = 1 .
When n = 2k, k OO N, for every vi vi 1 , vn v1 OO E(G) with i OO .
, 2, .
, n Oe .
, applies:
i Oe 1, i OO 1, 2, .
, 2n n n d.
i vi 1 , v1 ) = n Oe i, i OO 2 , 2 1, .
, n Oe 1 n v1 , v1 ) = 1 i Oe 1, i OO i vi 1 , v2 ) = i Oe 2, i OO 2, 3, .
, 2n n 1 Oe i, i OO n 1, n 2, .
, n Oe 1 d.
n v1 , v2 ) = 0 Because every edge in G has different representation with respect to W , then W is a bi-edge metric resolving set of G graph.
Next, it is shown that W is a bi-edge metric resolving set with minimal cardinality.
Take any S OI V (G) with |S| < |W |.
Suppose |S| = 1, without loss of generality, choose S = .
1 }, then there are two edges v1 v2 , vn v1 OO E(G) have the same representation with respect to S so that rbs .
1 v2 |S) = (.
, .
Oe .
) = rbs .
n v1 |S).
Consequently.
S is not a bi-edge metric resolving set of G graph.
So.
W is a bi-edge metric basis of G graph and e dimb (G) = 2.
n The bi-edge metric dimension of Kn graph with order n Ou 4 is n Oe 1.
The proof of e dimb (Kn ) = n Oe 1 is contained in Theorem 4.
INTERNATIONAL JOURNAL OF COMPUTING SCIENCE AND APPLIED MATHEMATICS VOL.
NO.
MARCH 2024
Theorem 4.
Let G be a complete with order n Ou 4, then e dimb (G) = n Oe 1.
Proof.
Let V (G) = vi .
OO .
, 2, 3, .
, .
with E(G) = vi v j .
, j OO .
, .
, .
i = j .
Let W = vi .
OO .
, 2, .
, .
OI V (G) with |W | = n Oe 1.
Without loss of generality, choose W = .
1 , v2 , .
, vnOe1 }.
Because G is complete, then there are as many n Oe 1 edges vn vk OO E(G) with k OO .
, 2, .
, n Oe .
which does not contain any vertex in W so that a bi-edge metric representation in G is obtained.
n v1 |W ) = 0, 1, 1, .
, 1 , n, n Oe 1, n Oe 1, .
, n Oe 1 | .
} rbs .
n v2 |W ) = 1, 0, 1, 1, .
, 1 , n Oe 1, n, n Oe 1, n Oe 1, .
, n Oe 1 | .
} nOe2 nOe2 nOe3 rbs .
n vnOe2 |W ) = nOe3 1, 1, .
, 1 , 0, 1 , n Oe 1, n Oe 1, .
, n Oe 1 , n, n Oe 1 | .
} nOe3 rbs .
n vnOe1 |W ) = nOe3 1, 1, .
, 1 , 0 , n Oe 1, n Oe 1, .
, n Oe 1 , n | .
} nOe2 nOe2 Because every edge in G has different representation with respect to W , then W is a bi-edge metric resolving set of G Next, it is shown that W is a bi-edge metric resolving set with minimal cardinality.
Take any S OI V (G) with |S| < |W |.
Suppose |S| = n Oe 2, without loss of generality, choose S = .
1 , v2 , .
, vnOe2 }, then there are two edges v1 vnOe1 , v1 vn OO E(G) have the same representation with respect to S so that rbs .
1 vnOe1 |S) = 0, 1, 1, .
, 1 , 0 , n Oe 1, n Oe 1, .
, n Oe 1 | .
} nOe1 v1 vnOe1 , v1 vn OO E(G) have the same representation with respect to S so that rbs .
1 vnOe1 |S) = = rbs .
1 vn |S).
1, 1, .
, 1 , 2, 2, .
, 2
| .
} | .
} nOe3 nOe3 Consequently.
S is not a bi-edge metric resolving set of G graph and every SA OI V (G) with |SA | < |S| is also not a bi-edge metric resolving set of G graph (Lemma .
So.
W is a bi-edge metric basis of G graph and e dimb (G) = n Oe 2.
n The bi-edge metric dimension of Pn graph with order n Ou 4 is one.
The proof of e dimb (Pn ) = 1 is contained in Theorem Theorem 6.
Let G be a path with order n Ou 4, then e dimb (G) = 1.
Proof.
Let V (G) = .
OO .
, 2, 3, .
, .
} with E(G) = .
i vi 1 .
OO .
, 2, .
, n Oe .
Choose W = .
1 } OI V (G), then for every vi vi 1 OO E(G) with i OO .
, 2, .
, n Oe .
applies d.
i , v1 ) = i Oe 1.
Because every edge in G has different representation with respect to W , then it is clear that W is a bi-edge metric basis of G graph and e dimb (G) = 1.
n i.
C ONCLUSION
From this research, the exact values of a bi-edge metric dimension are obtained for several special graphs, namely cycle, complete, star and path.
Based on the results that has been obtained, this research can be developed to determine the bi-edge metric dimension on graphs resulting such as graphs resulting from corona operations.
nOe2
ACKNOWLEDGMENT