On The Local Multiset Dimension of some Families of Graphs
RIDHO ALFARISI1,2, LILIEK SUSILOWATI2, DAFIK3, OSAYE J. FADEKEMI4
1Department of Elementary School Teacher Education, University of Jember,
Jl Kalimantan No. 37 Kampus Tegal Boto Jember 68121,
INDONESIA
2Department of Mathematics, Universitas Airlangga,
Surabaya,
INDONESIA
3Department of Mathematics Education, University of Jember,
Jl Kalimantan No. 37 Kampus Tegal Boto Jember 68121,
INDONESIA
4Department of Mathematics and Computer Science,
Alabama State University,
Jl Kalimantan No. 37 Kampus Tegal Boto Jember 68121,
USA
Abstract: Let be a connected graph. is said to be unicyclic if it contains exactly one cycle, and bicyclic if
the number of edges equals the number of vertices plus one. For a -ordered set ,
the multiset representation of a vertex in with respect to is given as
, where is the distance between and the ordered subset of
together with their multiplicities. The set is called a local -resolving set of if for every ,
. The local -resolving set with minimum cardinality is called the local multiset basis
and its cardinality is called the local multiset dimension of , denoted by . If has no local -
resolving set, we write and say that has an infinite local multiset dimension. In this paper, we
determine the local multiset dimension of the unicyclic and bicyclic graphs.
Key-Words: Networks infrastructure, local m-resolving set, local multiset dimension, unicyclic graphs, bicyclic
graphs.
Received: September 24, 2022. Revised: November 11, 2022. Accepted: December 6, 2022. Published: January 17, 2023.
1 Introduction
In this paper, we consider graphs that are simple,
connected and finite. The vertex set and edge set are
denoted, respectively, as and . The
distance between u and v, denoted as or
simply as , is the length of the shortest path
between and in . A vertex is said to resolve a
pair if . A subset
is then said to be a resolving set of if
any pair of adjacent vertices of can be resolved by
some vertex in . The set with minimum
cardinality in is called a metric basis and its
cardinality is the metric dimension of , denoted as
by [2].
A new variant of the resolving set problems
introduced by Okamoto et al., [9], is the local
resolving set problems. For a -ordered set,
, the vertex representations of
vertex to the set is an ordered -tuple,
. The
set W is called a local resolving set if
. The minimum
cardinality of a local resolving set is called local
basis and its cardinality is called the local metric
dimension of , denoted by .
Both the revolving set problems and the local
set resolving problems are topics in distances in
graphs that have increased in popularity over the
past few decades due to their applications in many
real-life problems, especially in network
infrastructures, chemical structures, computer
connectivity and navigation robots optimization
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.8
Ridho Alfarisi, Liliek Susilowati, Dafik, Osaye J. Fadekemi
E-ISSN: 2224-2880
64
Volume 22, 2023
problems. More detail about these applications can
be seen in Khuller et al., [1].
A generalized form of the local resolving set
problem is the multiset dimension of a graph first
defined by Simanjuntak et al., [3]. The multiset
dimension of a graph is defined as the set
, such that the vertex
representations of a vertex to the set is
the multiset,
where is the
length of the shortest path between and a vertex in
together with their multiplicities. The set is
called an -resolving set if ,
. If has an -resolving set,
then the minimum resolving set is a multiset
basis of and its cardinality is called the multiset
dimension of , denoted as . Otherwise, we
say that has an infinite multiset dimension and we
write
Several results on multiset dimensions can be
found in the literature. For example, for multiset
dimensions at least 3 were proven by Bong et al.,
[12], for almost hypercube graphs by Alfarisi et al.,
[5], trees by Hafidh et al., [11], starphene and
zigzag-edge coronoid by Liu et al., [13]. A new
notion based on the multiset dimension of was
defined by Alfarisi et al., [4], as the local multiset
dimension.
As in previous definitions, for a given set
, the vertex
representations of a vertex to the set is
. The
set is called a local -resolving set of if
for . The
minimum cardinality of a local -resolving set is
called the and its cardinality
is called the , denoted by
: otherwise, we say that has an infinite
local multiset dimension and we write
.
We illustrate this concept in Fig. 1. In this
case, we have the resolving set , shown
in Fig. 1(a) whose metric dimension is .
Furthermore, the -resolving set is
, shown in Fig. 1(b) with multiset
dimension, . The representations of
with respect to are all distinct. We only
need to make sure the adjacent vertices have distinct
representations for the local multiset dimension.
Thus, we have the local -resolving ,
shown in Fig. 1(c) that the local multiset dimension
is . The vertex representation with
respect to basis can be seen in Fig.1. In Fig. 1(a) and
(b), every vertex in has distinct representations.
For Fig. 1(c), every two adjacent vertices have a
different representation.
Fig. 1: (a) A graph with metric dimension 2; (b) A
graph with multiset dimension 3; (c) A graph with
local multiset dimension 1.
The natural question what the local multiset
dimension of some special graphs namely paths,
stars, trees and cycles and also the local multiset
dimension of graph operations namely, the cartesian
product was answered, for example, in a classical
paper by Alfarisi et al., [4]. Other known results are,
for example, the -shadow graph by Adawiyah et
al., [8], and the local multiset dimension of
unicyclic graphs was also studied by Adawiyah et
al., [7].
This paper aims to provide similar results for
the unicyclic and bicyclic graphs. In particular, we
show that if is a unicyclic graph of order ,
then is 1 for even and 2 for odd.
Similarly, if is bicyclic with cycles of order
, then is 1 if both and are
even, and 2 otherwise.
The following known definitions and results
will be useful in the proof of our main results.
Proposition 1.1 [10] A graph is bipartite if and only
if it contains no odd cycle.
Proposition 1.2 [4] Let be a complete graph
with . Then .
Proposition 1.3 [6] Let be a connected graph.
Then if and only if is a bipartite
graph.
Definition 1.1 The unicyclic graph is a graph that
has only one cycle.
Definition 1.2 The bicyclic graph is a graph that has
only two cycles.
By Definition 1.1, it is obvious that the
unicyclic graph can be obtained from a tree by
connecting any two vertices by an edge. An
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.8
Ridho Alfarisi, Liliek Susilowati, Dafik, Osaye J. Fadekemi
E-ISSN: 2224-2880
65
Volume 22, 2023
example of a unicyclic graph (left) and a bicyclic
graph (right) can be seen in Fig. 2.
Fig. 2: Unicyclic (left) and bicyclic (right) graphs
2 Results and Discussion
In this section, we investigate the local multiset
dimension of a unicyclic and bicyclic graph.
2.1 For Unicyclic Graphs
Let be a unicyclic graph obtained from a tree by
adding an edge between two non-adjacent
vertices . We state our first results for
both even and odd cycle subgraphs of
Proposition 2.1 Let be a unicyclic graph that
contains an even cycle. Then .
Proof. Let be the cycle subgraph of , where is
the number of vertices in . If is even, then is
bipartite by Proposition 1.1 and by
Proposition 1.3
Lemma 2.1 Let be a unicyclic graph that contains
an odd cycle . For every , there exists
exactly one pair of adjacent vertices and
satisfying where and are in a
cycle .
Proof. Let be a unicyclic graph containing an odd
cycle where . Suppose
and
with for . Let
. Then is a disconnected graph that
contains components where each component is a
tree. For , we define as the
component of containing vertex .
Suppose is a vertex in , then there are
such that . Suppose and
are two adjacent vertices in and there are
such that , then
for . Since
are a tree and every two distinct vertices in the
tree have a unique path between them, we get that
either or ,
which implies . Therefore, and
must be two different components of , implying
that and must be in .
Now let and be two adjacent vertices at
and . Suppose
, then or
, which implies
. So, . When is
odd, two adjacent vertices are obtained, namely
and where both indices are at
modulo .
Suppose there are two distinct pairs of
adjacent vertices and of such that for
any vertices and
. With the same arguments
above, we get that ,
and ,
come from
different cycles in . Therefore, contains at least
two cycles which is a contradiction.
Theorem 2.1 Let be a unicyclic graph of order at
least . If contains a circle of order , then
Proof. Let be a cycle of . We consider two
cases for as follows.
Case 1. For even
Since is even, is a bipartite graph by Proposition
1.3 and by Proposition 2.1.
Case 2. For odd.
If is odd, then is not bipartite based on
Proposition 1.1 implying that by
Proposition 1.3. Furthermore, we will prove the
upper bound of the local multiset dimension of
that . Let be a cycle contained in
. By Lemma 2.1, there is exactly one pair of and
adjacent vertices in such that
for every . Now, define
and . Since no two
adjacent vertices have the same representation of ,
is a local multiset resolving set of and thus,
.
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.8
Ridho Alfarisi, Liliek Susilowati, Dafik, Osaye J. Fadekemi
E-ISSN: 2224-2880
66
Volume 22, 2023
Fig. 3: (a) with is odd and (b)
with is even
2.2 For Bicyclic Graphs
Let be a bicyclic graph. Recall that a bicyclic
graph is obtained from a tree by adding two edges
say, and with two non-
adjacent vertices and
, respectively. In other words, a bicyclic graph
is a graph that contains only two cycle subgraphs.
Suppose is the number of vertices in the cycle
subgraph and is the number of vertices in the
cycle subgraph .
It is important to note the following
conditions for the type of bicycle graph with and
being considered.
1. the bicyclic graph contains two disjoint
cycles.
2. and are disjoint with the property that
. The example can be
seen in Fig. 4.
For conditions 1 and 2, if and are even,
then is a bipartite graph, and so by Proposition
1.3, . Our next lemma shows the
condition if at least one of and is odd.
Fig. 4: Bicyclic graph with cycle and is
disjoint with properties Ø
Lemma 2.2. Let G be a bicyclic graph that contains
an odd cycle or . For every , there
exists exactly one pair of adjacent vertices and
that satisfy where and are in
an odd cycle or .
Proof. Let be a unicyclic graph containing an odd
cycle or where . Suppose
,
and
with
for and for . Let
be a
subgraph of such that
. So,
is
a disconnected graph that contains
components where each component is a tree. For
, we define as the component
of
containing vertex
Suppose is a vertex in , then there are
such that . Suppose
and are two adjacent vertices in and there are
such that , then
for
. Since is a tree and every two distinct
vertices in the tree have a unique path between
them, we get that either or
, which implies
. Therefore, and must be two different
components of
. Hence, and must be in .
Let and be two adjacent vertices at
and . Suppose
, then or ,
which implies . So,
. When is odd, two adjacent vertices
are obtained, namely and
where both indices are at modulo .
Furthermore, we have the properties of two
odd cycles or in Observation 2.1 as follows.
Observation 2.1 Let be a bicyclic graph that
contains an odd cycle or . For is odd and
is even (or is even and is odd). We have some
properties as follows.
1. We define two vertices with
and where there is a path
. This path is called a bridge, denoted by .
2. If is even, then for two
adjacent vertices .
3. For , since is a tree and
every two distinct vertices in the tree have a
unique path between them, we get that either
or ,
which implies .
Theorem 2.2 Let be a bicyclic graph of order at
least . If contains cycles of order and , then
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.8
Ridho Alfarisi, Liliek Susilowati, Dafik, Osaye J. Fadekemi
E-ISSN: 2224-2880
67
Volume 22, 2023
Proof. Let and be a cycle graph of . There
are three cases for and as follows.
Case 1. If and are even
Because and are even, then is a bipartite
graph, based on Proposition 1.3 that
Fig. 5: with and are even
Case 2. If is odd and is even.
If is odd, then is not a bipartite graph, resulting
in 2. Furthermore, we will prove the
upper bound of the local multiset dimension of
that . Let and be cycles
contained in . By Lemma 2.2, there is exactly one
pair of and adjacent vertices in or such
that for every . Now,
define and .
We show that vertex representation for two adjacent
vertices is distinct as follows.
1. For two adjacent vertices ,
and .
Thus, .
2. For two adjacent vertices ,
by Observation 2.1 (3),
implying that and
. Thus,
.
3. For two adjacent vertices in a bridge, say,
, implying
that and
. Thus, .
4. For two adjacent vertices in , i.e.
, by Observation 2.1
(2) implying that and
. Thus,
.
5. For two adjacent vertices in and
, and
by Observation 2.1 (3) implying that
and ,
respectively. Thus, .
It is easy to see that by Equations 1. to 5.
above, is a local m-resolving set of . Hence,
Case 3. If and are odd.
If and are odd, then is not a bipartite graph,
implying that . Furthermore, we will
prove the upper bound of the local multiset
dimension of that . Let and be
cycles contained in . By Lemma 2.2, there is
exactly one pair of and adjacent vertices in
or such that for every
. Now, define and
with . We show
that vertex representation for two adjacent vertices
is distinct as follows.
1. For two adjacent vertices ,
and
and so . Thus,
.
2. For two adjacent vertices , based
on Observation 2.1 (3) that
then . Since
, then .
Thus, .
3. For two adjacent vertices in bridges
, , then
and then
. Thus,
.
4. For two adjacent vertices ,
and
then . Thus,
.
5. For two adjacent vertices in and
, based on Observation 2.1 (3) that
then
. Since then
. Thus,
.
Based on Equations 1 to 5 above show that
is a local $m$-resolving set of . Therefore,
3 Conclusion
In this paper, the local multiset dimensions of
unicyclic graphs and bicyclic graphs in which the
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.8
Ridho Alfarisi, Liliek Susilowati, Dafik, Osaye J. Fadekemi
E-ISSN: 2224-2880
68
Volume 22, 2023
cycles have no common vertex have been studied.
Based on the results of this research, we propose the
following open problem.
Open Problem 3.1 Characterise the local multiset
dimension of bicyclic graphs in which the two cycles
have at least one vertex in common.
Acknowledgment:
We gratefully acknowledge the support from
Universitas Jember and Universitas Airlangga for
the year 2023.
References:
[1] S. Khuller, B. Raghavachari and A.
Rosenfeld, Localization in Graphs, Technical
Report CS-Tr-3326, University of Maryland
at College Park, 1994.
[2] G. Chartrand, L. Eroh, M. Johnson, and O. R.
Oellerman, Resolvability in graphs and the
metric dimension of a graph, Discrete Applied
Mathematics, Vol. 105, 2000, pp. 99-113.
[3] R. Simanjuntak, P. Siagian, and T. Vetrik.
The multiset dimension of graphs. arXiv
preprint arXiv:1711.00225, 2017.
[4] R. Alfarisi, Dafik, A. I. Kristiana, and I. H.
Agustin, The Local Multiset Dimension of
Graphs. IJET, Vol. 8. No. 3, 2019, pp.120-
124.
[5] R. Alfarisi, Y. Lin, J. Ryan, Dafik, I. H.
Agustin, A Note on Multiset Dimension and
Local Multiset Dimension of Graphs,
Statistics, Optimization and Information
Computing, Vol. 8, No. 4, 2020, pp. 890-901.
[6] R. Alfarisi, L. Susilowati, Dafik, The Local
Multiset Resolving of Graphs. 2022.
Accepted.
[7] R. Adawiyah, R. M. Prihandini, E. R. Albirri,
I. H. Agustin, and R. Alfarisi, The local
multiset dimension of a unicyclic graph. In
IOP Conf. Series: EES, Vol. 243, No. 1, 2019,
p. 012075.
[8] R. Adawiyah, I. H. Agustin, R. M. Prihandini,
R. Alfarisi, and E. R. Albirri, On the local
multiset dimension of an m-shadow graph. In
Journal of Physics: Conf. Series, Vol. 1211,
No. 1, 2019, p. 012006.
[9] F. Okamoto, B. Phinezy, P. Zhang. The Local
Metric Dimension of A Graph, Mathematica
Bohemica, Vol. 135, No. 3, 2010, 239 – 255.
[10] R. Diestel, Graph Theory, Graduate Texts in
Mathematics, Springer, ISBN 978-3-642-
14278-91, 2016.
[11] Y. Hafidh, R. Kurniawan, S. Saputro, R.
Simanjuntak, S. Tanujaya, & S.
Uttunggadewa, S. Multiset Dimensions of
Trees. arXiv preprint arXiv:1908.05879,
2019.
[12] N. H. Bong, and Y. Lin. Some properties of
the multiset dimension of graphs, Electron. J.
Graph Theory Appl, Vol. 9, No. 1, 2021, 215-
221.
[13] J. B. Liu, S. K. Sharma, V. K. Bhat, and H.
Raza. Multiset and Mixed Metric Dimension
for Starphene and Zigzag-Edge Coronoid.
Polycyclic Aromatic Compounds, 2021, pp. 1-
15.
Contribution of Individual Authors to the
Creation of a Scientific Article (Ghostwriting
Policy)
-Ridho Alfarisi, carried out the conceptualization,
formal analysis, methodology, and writing-original
draft.
-Liliek Susilowati carried out the methodology,
supervision, funding acquisition, writing review and
editing.
-Dafik carried out the supervision and writing
review and editing.
-Osaye J. Fadekemi carried out the formal analysis
and writing review and editing.
Sources of Funding for Research Presented in a
Scientific Article or Scientific Article Itself
This research was supported by Universitas
Airlangga and University of Jember.
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.8
Ridho Alfarisi, Liliek Susilowati, Dafik, Osaye J. Fadekemi
E-ISSN: 2224-2880
69
Volume 22, 2023
Conflict of Interest
The authors have no conflicts of interest to declare
that are relevant to the content of this article.
Creative Commons Attribution License 4.0
(Attribution 4.0 International, CC BY 4.0)
This article is published under the terms of the
Creative Commons Attribution License 4.0
https://creativecommons.org/licenses/by/4.0/deed.en
_US
