ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 23 (2023) #P2.08
https://doi.org/10.26493/1855-3974.2568.55c
(Also available at http://amc-journal.eu)
On metric dimensions of hypercubes
Aleksander Kelenc *
University of Maribor, FERI, Koroška cesta 46, 2000 Maribor, Slovenia and
Institute of Mathematics, Physics and Mechanics, Jadranska 19, 1000 Ljubljana, Slovenia
Aoden Teo Masa Toshi
Independent researcher, Singapore
Riste Škrekovski †
University of Ljubljana, FMF, Jadranska 19, 1000 Ljubljana, Slovenia and
Faculty of Information Studies, Ljubljanska cesta 31a, 8000 Novo Mesto, Slovenia
Ismael G. Yero ‡
Universidad de Cádiz, Departamento de Matemáticas, Av. Ramón Puyol, s/n,
11202 Algeciras, Spain
Received 24 February 2021, accepted 25 July 2022, published online 2 December 2022
Abstract
In this note we show two unexpected results concerning the metric, the edge metric
and the mixed metric dimensions of hypercube graphs. First, we show that the metric and
the edge metric dimensions of Qd differ by at most one for every integer d. In particular,
if d is odd, then the metric and the edge metric dimensions of Qd are equal. Second, we
prove that the metric and the mixed metric dimensions of the hypercube Qd are equal for
every d ≥ 3. We conclude the paper by conjecturing that all these three types of metric
dimensions of Qd are equal when d is large enough.
Keywords: Edge metric dimension, mixed metric dimension, metric dimension, hypercubes.
Math. Subj. Class. (2020): 05C12, 05C76
*Corresponding author. Partially supported by the Slovenian Research Agency ARRS via grants J1-1693 and
J1-2452.
†Acknowledges the Slovenian research agency ARRS, program No. P1–0383 and project No. J1-3002.
‡Partially supported by the Spanish Ministry of Science and Innovation through the grant PID2019-105824GB-
I00.
E-mail addresses: aleksander.kelenc@um.si (Aleksander Kelenc), aodenteo@gmail.com (Aoden Teo Masa
Toshi), skrekovski@gmail.com (Riste Škrekovski), ismael.gonzalez@uca.es (Ismael G. Yero)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
2 Ars Math. Contemp. 23 (2023) #P2.08
1 Introduction
The metric dimension of connected graphs was introduced about 50 years ago in [6, 22],
in connection with modeling navigation systems in networks, although this notion was
already known by then for general metric spaces from [1]. Given a connected graph G
and two vertices u, v ∈ V (G), the distance dG(u, v) between these two vertices is the
length of a shortest path connecting v and u. The vertices u, v are distinguished or resolved
by a vertex x ∈ V (G) if dG(u, x) ̸= dG(v, x). A given set of vertices S is a metric
generator for the graph G, if every two vertices of G are distinguished by a vertex of S.
The cardinality of the smallest possible metric generator for G is the metric dimension of
G, which is denoted by dim(G). The terminology of metric generators was introduced in
[11], and the previous two works referred to such sets as resolving sets and locating sets,
respectively. We herewith follow the terminology of [11]. A metric generator for G of
cardinality dim(G) is called a metric basis. Although the classical metric dimension is an
old topic in graph theory, there are still several open problems that remain unsolved. Recent
investigations on this concern are [3, 4, 8, 16]. More results and open questions concerning
metric dimension and related variants can be found in the recent surveys [15] and [23].
In order to uniquely identify the edges of a graph, by using vertices, the edge metric
dimension of connected graphs was introduced in [10] as follows. Let G be a connected
graph and let uv be an edge of G such that u, v ∈ V (G). The distance between a vertex
x ∈ V (G) and the edge uv is defined as, dG(uv, x) = min{dG(u, x), dG(v, x)}. It is said
that two distinct edges e1, e2 ∈ E(G) are distinguished or resolved by a vertex v ∈ V (G)
if dG(e1, v) ̸= dG(e2, v). A set S ⊂ V (G) is called an edge metric generator for G if
and only if for every pair of edges e1, e2 ∈ E(G), there exists an element of S which
distinguishes the edges. The cardinality of a smallest possible edge metric generator of
a graph is known as the edge metric dimension, and is denoted by edim(G). After the
seminal paper [10], a significant number of researches on such parameter have appeared.
Among them, some of the most recent ones are [3, 12, 13, 14, 19]. See also the survey
[15] for some other contributions. It is natural to consider comparing the metric and edge
metric dimensions of graphs. However, as first proved in [10], and continued in [13, 14],
both parameters are not in general comparable since there exist connected graphs G for
which edim(G) < dim(G), edim(G) = dim(G) or edim(G) > dim(G).
In order to combine the unique identification of vertices and of edges in only one
scheme, the mixed metric dimension of graphs was introduced in [9]. For a connected
graph G, a vertex w ∈ V (G) and an edge uv ∈ E(G) are distinguished or resolved by
a vertex x ∈ V (G) if dG(w, x) ̸= dG(uv, x). A set S ⊂ V (G) is called a mixed metric
generator for G if and only if for every pair of elements of the graphs (vertices or edges)
e, f ∈ E(G)∪V (G), there exists a vertex of S which distinguishes them. The cardinality of
a smallest possible mixed metric generator of G is known as the mixed metric dimension of
G, and is denoted by mdim(G). Some recent studies on mixed metric dimension of graphs
are [20, 21]. Clearly, every mixed metric generator must be a metric generator as well
as an edge metric generator, and so, mdim(G) ≥ max{dim(G), edim(G)}, for any con-
nected graph G. Moreover, since dim(G) and edim(G) are in general not comparable (see
[13, 14] for more information on this fact), several situations relating these three parame-
ters can be found. That is, there are graphs G with mdim(G) ≫ max{dim(G), edim(G)},
mdim(G) = dim(G) ≫ edim(G), mdim(G) = edim(G) ≫ dim(G), or mdim(G) =
dim(G) = edim(G).
A. Kelenc et al.: On metric dimensions of hypercubes 3
The metric dimension of hypercube graphs has attracted the attention of several re-
searchers from long ago. For instance, the work of Lindström [17] is probably one of the
oldest ones, and for some recent ones we suggest the works [7, 18, 24]. Surprisingly, for
other related invariants there has been comparatively little research on hypercube graphs,
although one can find some interesting recent results on this topic such as those that ap-
peared in [5, 7]. It is our goal to present some results on the close connections that exist
among the metric, the edge metric and the mixed metric dimensions of hypercube graphs.
The d-dimensional hypercube, denoted by Qd, with d ∈ N, is a graph whose vertices
are represented by d-dimensional binary vectors, i.e., u = (u1, . . . , u2) ∈ V (Qd) where
ui ∈ {0, 1} for every i ∈ {1, . . . , d}. Two vertices are adjacent in Qd if their vectors differ
in exactly one coordinate. Hypercubes can be also seen as the d times Cartesian product
of the graph P2, that is, Qd ∼= P2□P2□ · · ·□P2, or recursively, Qd ∼= Qd−1□P2. The
distance between two vertices in Qd represents the total number of coordinates in which
their vectors differ. The hypercube Qd is bipartite, and has 2d vertices and d · 2d−1 edges.
We remark that Q2 is the cycle C4 and that Q4 can be also seen as the torus graphs C4□C4.
2 Results
Our first contribution is to relate the metric generators with the edge metric generators of
bipartite graphs.
Lemma 2.1. Let G be a connected bipartite graph. Then, every metric generator for G is
also an edge metric generator.
Proof. Let S be an arbitrary metric generator for G. We will show that S is an edge metric
generator as well.
Let e1 = x1y1 and e2 = x2y2 be two arbitrary distinct edges of G. Since G is bipartite
and e1, e2 are distinct, one can w.l.o.g. assume that x1, x2 (with x1 ̸= x2) belong to one
of the bipartition sets and y1, y2 to the other one. Hence the distance between u = x1 and
v = x2 is even.
Now, as u and v are distinct, there must be a vertex s ∈ S that distinguishes them,
i.e. d(s, u) ̸= d(s, v). We may assume that d(s, u) + 1 ≤ d(s, v). Since u and v are on
even distance, it follows that distances d(s, u) and d(s, v) are of same parity, otherwise we
encounter a closed walk of odd length in G, which is not possible in a bipartite graph. This
implies d(s, u) + 2 ≤ d(s, v), and now we easily derive
d(e1, s) ≤ d(u, s) < d(v, s)− 1 ≤ d(e2, s).
In particular, d(e1, s) < d(e2, s) implies that e1, e2 are distinguished by s ∈ S. Since
the choice of these two edges was arbitrary, we conclude that S is also an edge metric
generator.
It is then natural to think in the opposite direction with regard to the result above. In
particular, we ask if an edge metric generator for a bipartite graph is also a metric generator.
In contrast with the result above, achieving this seems to be a challenging task. However,
we have at least managed to show a weaker result for an infinite family of bipartite graphs,
namely the hypercubes Qd. That is, when d is odd, every edge metric generator for Qd is
indeed a metric generator, and when d is even, every edge metric generator is “almost” a
metric generator.
4 Ars Math. Contemp. 23 (2023) #P2.08
From now on we denote by αi the vector of dimension d whose ith-coordinate is 1,
and the remaining coordinates are 0. Also, by “⊕” we represent the standard (binary)
XOR operation. Notice that, for any vertex u ∈ V (Qd), u ⊕ αi means switching the
ith-coordinate of u from 0 to 1, or vice versa.
Lemma 2.2. Let S be an edge metric generator of Qd. If there exist two distinct vertices u
and v not distinguished by S, then they must be antipodal in Qd and d is even. If d is odd,
then S is also a metric generator of Qd.
Proof. Suppose that u = (u1, u2, . . . , ud) and v = (v1, v2, . . . , vd) are not antipodal.
Then, ui = vi for some i. Let Q0d−1 and Q
1
d−1 be the half-cubes regarding the dimension
i. Notice that u and v belongs to a same half-cube, say Q0d−1. Let eu and ev be the edges
corresponding to the component i (in Qd) incident with u and v, respectively. In other
words, as u⊕αi and v⊕αi are the neighbours of u and v in Q1d−1, we have eu = (u, u⊕αi)
and ev = (v, v⊕αi). We claim that the edges eu and ev are not distinguished by S. To see
this, observe that if s ∈ S belongs to Q0d−1, then
d(s, eu) = d(s, u) = d(s, v) = d(s, ev).
Also, if s ∈ S belongs to Q1d−1, then
d(s, eu) = d(s, u⊕ αi) = d(s, v ⊕ αi) = d(s, ev).
We hence derive that the edges eu and ev are not distinguished by S, which is a contradic-
tion.
Based on the above arguments we conclude that u and v are antipodal, i.e. d(u, v) =
d. Hence, every vertex x of S satisfies d(u, x) + d(x, v) = d. As every vertex s ∈ S
must be equally distanced from u and v, we conclude that d(u, s) = d(s, v) = d/2, and
consequently, d must be even. This establishes the main claim.
Finally, observe that if d is odd, then no vertex is equally distanced from two antipodal
vertices of Qd, and therefore, S is a metric generator of Qd.
Next lemma will ensure that enlarging an edge metric generator of Qd with one chosen
element, we get a metric generator of Qd.
Lemma 2.3. Let S be an edge metric generator of Qd and let s be an arbitrary element of
S. Then, S ∪ {s⊕ α1} is a metric generator of Qd.
Proof. If S is a metric generator of Qd, then S∪{s⊕α1} is so too, and we are done. Thus,
we assume that S is not a metric generator of Qd. Then, by Lemma 2.2, d is even and there
must exist antipodal vertices u and v such that d(u, x) = d(v, x) = d/2 for every x ∈ S.
This will not be the case for s ⊕ α1, as |d(u, s ⊕ α1) − d(v, s ⊕ α1)| = 2. Therefore, we
conclude that S ∪ {s⊕ α1} is a metric generator of Qd.
Since Qd is a bipartite graph, the two previous lemmas give us the following conse-
quence.
Theorem 2.4. Let d ≥ 1. Then
edim(Qd) ≤ dim(Qd) ≤ edim(Qd) + 1,
with the second inequality being tight only if d is even.
A. Kelenc et al.: On metric dimensions of hypercubes 5
Proof. The lower bound holds by Lemma 2.1. The upper bound and its possible tightness
(for more than one case) follows by Lemmas 2.2 and 2.3.
Notice that the upper bound dim(Qd) ≤ edim(Qd) + 1 is indeed tight for the case Q4,
since 4 = dim(Q4) = edim(Q4) + 1, as proved in [10].
We now turn our attention to relating the metric dimension with the mixed metric di-
mension of hypercubes. To this end, we will need the following two results. We must
remark that the first of next two lemmas already appeared in [18]. We include its proof for
completeness.
Lemma 2.5. If S is a metric generator (in particular, a metric basis) of Qd and s ∈ S,
then (S \{s})∪{s′} is also a metric generator (in particular, a metric basis) of Qd, where
s′ ∈ V (Qd) is the antipodal vertex of s.
Proof. If s ∈ S distinguishes some pair of vertices x and y of Qd, then s′ distinguishes
such pair as well, since d(x, s′) = d− d(x, s) and d(y, s′) = d− d(y, s). This also means
that no metric basis of Qd contains two antipodal vertices. Thus, if S is a metric generator
(or a metric basis) of Qd, then S \ {s} ∪ {s′} is a metric generator (or a metric basis) as
well.
Lemma 2.6. If S is a metric generator of Qd, then there is at most one index i ∈ {1, . . . , d}
such that all the vertices from S have the same value at the ith coordinate.
Proof. Suppose that there exist two different indices i and j such that all vertices from S
have the same value at the ith and jth coordinates. First, let us consider the case when
there are zeroes at such coordinates. Other cases can be shown by using similar arguments.
Now, let x ∈ V (Qd) be a vertex having zeroes at all coordinates, except at the ith, and let
y be a vertex having zeroes at all positions except at the jth. Then, d(x, s) = d(y, s) for
any vertex s ∈ S, a contradiction.
The mixed metric dimension of hypercubes Q1 and Q2 are 2 and 3, respectively. This
can be derived from results for paths and cycles from [9]. This gives us that dim(Qd) <
mdim(Qd), for d ∈ {1, 2}. For all higher dimensions the mixed metric dimension is equal
to the metric dimension as we next show.
Theorem 2.7. Let d ≥ 3. Then
dim(Qd) = mdim(Qd).
Proof. First, {(1, 1, 1), (0, 1, 0), (0, 0, 1)} and {(1, 1, 1, 1), (0, 1, 0, 0), (0, 0, 1, 0),
(0, 0, 0, 1)} are mixed metric bases for Q3 and Q4, respectively. Thus, the equality follows
for these cases since dim(Q3) = 3 and dim(Q4) = 4. It remains to check the equality for
d ≥ 5.
Let S be a metric basis for Qd with d ≥ 5. By Lemma 2.1, S is an edge metric
generator of Qd. In this sense, in Qd we only need to distinguish those pairs of elements,
one of them being a vertex and the other one, an edge. For this, let u be an arbitrary vertex
and let e = xy be an arbitrary edge of Qd.
Suppose first that u is not a vertex of e. As d(u, x) and d(u, y) are of different parity,
we may assume that u and x are on even distance. Now, let si be a vertex from S that
6 Ars Math. Contemp. 23 (2023) #P2.08
distinguishes u and x. Similarly, as in Lemma 2.1, notice that d(si, u) and d(si, x) are of
the same parity, and as they are different, we have that |d(si, u) − d(si, x)| ≥ 2. So, if
d(si, u) < d(si, x), then we derive
d(si, u) < d(si, u) + 1 ≤ d(si, x)− 1 ≤ d(si, e),
and if d(si, x) < d(si, u), then we have
d(si, e) ≤ d(si, x) < d(si, u).
Thus, in both cases e and u are distinguished by a vertex from S.
So all the pairs of elements (vertices and edges) considered in the upper part are distin-
guished by an arbitrary metric basis. To conclude the proof, we need to construct a metric
basis of cardinality |S| that will also distinguish incident vertices and edges.
Suppose now that u is an endpoint of e, say u = x. To distinguish u and e there needs
to be a vertex s ∈ S which is from the half-cube Qd−1 that contains vertex y and does not
contain vertex x. To distinguish all such pairs there must be at least one vertex from the
mixed metric generator in every half-cube Qd−1. For any index i ∈ {1, . . . , d}, there exists
a vertex from a mixed metric generator having 0 on the ith coordinate, and a vertex from
a mixed metric generator having 1 on the ith coordinate. In other words, a mixed metric
basis does not have a column of zeroes or a column of ones at an arbitrary index i (if we
arrange all vectors of the mixed metric basis as a matrix with such vectors as the rows of
such matrix).
We have started from an arbitrary metric basis S. Since Qd is a vertex transitive graph,
we may assume that the vertex s1 = (0, 0, . . . , 0) (all coordinates equal to 0) is in S. If
S does not contain a column of zeroes, then S is also a mixed metric basis. Otherwise,
by Lemma 2.6, there exists only one such column, say at index i0. By Lemma 2.5, we
know that we can replace any of the vertices from the set S with its antipodal vertex and
the incurred set S′ = S \ {s} ∪ {s′} is a metric basis too, since the column at index i0 (all
zeroes) ensures that no two vertices in S are antipodal to each other. Moreover, in view of
Lemma 2.1, S is an edge metric generator as well.
There exist at least four different vertices s1 = (0, 0, . . . , 0), s2, s3 and s4 in the set S,
since dim(Qd) ≥ 4, for d ≥ 5. We construct four sets S′i in the following way:
S′1 = (S \ {s1}) ∪ {s′1}, S′2 = (S \ {s2, s3}) ∪ {s′2, s′3},
S′3 = (S \ {s2}) ∪ {s′2}, S′4 = (S \ {s1, s3}) ∪ {s′1, s′3},
and consider the next situations:
(I): If S′1 is not a mixed metric generator, then there is a column of ones in S′1 at some
index i1.
(II): If S′2 is not a mixed metric generator, then there is a column of zeroes in S′2 at some
index i2.
(III): If S′3 is not a mixed metric generator, then there is a column of zeroes in S′3 at some
index i3.
(IV): If S′4 is not a mixed metric generator, then there is a column of ones in S′4 at some
index i4.
Observe that all these indices i0, i1, i2, i3, and i4 are different. If none of the four sets
S′i defined above is a mixed metric generator, then the initial set S looks as follows.
A. Kelenc et al.: On metric dimensions of hypercubes 7
i0 i1 i2 i3 i4 . . .
s1 : 0 0 0 0 0 . . .
s2 : 0 1 1 1 1 . . .
s3 : 0 1 1 0 0 . . .
s4 : 0 1 0 0 1 . . .
...
...
...
...
...
...
s|S| : 0 1 0 0 1 . . .
We now take a look at the columns i1, i2, i3 and i4. Let v1 be a vertex having zeroes at
all positions except at i1 and i3 and let v2 be a vertex having zeroes at all positions except
at i2 and i4. Then, d(v1, s) = d(v2, s), for any vertex s ∈ S, a contradiction. Therefore,
at least one of the sets S′i has to be a mixed metric generator, and therefore, the equality
mdim(Qd) = dim(Qd) follows since any mixed metric basis is also a metric basis.
In view of the asymptotical result for the metric dimension of hypercubes from [2],
Theorems 2.4 and 2.7 give us the following consequences.
Corollary 2.8. Let d ≥ 3. Then
dim(Qd)− 1 ≤ edim(Qd) ≤ dim(Qd) = mdim(Qd).
Corollary 2.9. Let d ≥ 2. Then
mdim(Qd) ∼ edim(Qd) ∼ dim(Qd) ∼
2d
log2 d
.
We conclude this short paper with the following conjecture.
Conjecture 2.10. If d is large enough, then
edim(Qd) = dim(Qd).
As the above conjecture does not hold for d = 4, d must be at least 5.
ORCID iDs
Aleksander Kelenc https://orcid.org/0000-0003-1633-9845
Riste Škrekovski https://orcid.org/0000-0001-6851-3214
Ismael G. Yero https://orcid.org/0000-0002-1619-1572
References
[1] L. Blumenthal, Theory and Applications of Distance Geometry, Oxford University Press, Ox-
ford, 1953.
[2] D. G. Cantor and W. H. Mills, Determination of a subset from certain combinatorial properties,
Can. J. Math. 18 (1966), 42–48, doi:10.4153/cjm-1966-007-2, https://doi.org/10.
4153/cjm-1966-007-2.
[3] J. Geneson, Metric dimension and pattern avoidance in graphs, Discrete Appl. Math. 284
(2020), 1–7, doi:10.1016/j.dam.2020.03.001, https://doi.org/10.1016/j.dam.
2020.03.001.
8 Ars Math. Contemp. 23 (2023) #P2.08
[4] G. Gutin, M. S. Ramanujan, F. Reidl and M. Wahlström, Alternative parameterizations of
metric dimension, Theor. Comput. Sci. 806 (2020), 133–143, doi:10.1016/j.tcs.2019.01.028,
https://doi.org/10.1016/j.tcs.2019.01.028.
[5] A. Hakanen, V. Junnila and T. Laihonen, The solid-metric dimension, Theor. Comput. Sci. 806
(2020), 156–170, doi:10.1016/j.tcs.2019.02.013, https://doi.org/10.1016/j.tcs.
2019.02.013.
[6] F. Harary and R. A. Melter, On the metric dimension of a graph, Ars Comb. 2 (1976), 191–195.
[7] A. Hertz, An IP-based swapping algorithm for the metric dimension and minimal dou-
bly resolving set problems in hypercubes, Optim. Lett. 14 (2020), 355–367, doi:10.1007/
s11590-017-1184-z, https://doi.org/10.1007/s11590-017-1184-z.
[8] Z. Jiang and N. Polyanskii, On the metric dimension of Cartesian powers of a graph, J. Comb.
Theory, Ser. A 165 (2019), 1–14, doi:10.1016/j.jcta.2019.01.002, https://doi.org/10.
1016/j.jcta.2019.01.002.
[9] A. Kelenc, D. Kuziak, A. Taranenko and I. G. Yero, Mixed metric dimension of graphs, Appl.
Math. Comput. 314 (2017), 429–438, doi:10.1016/j.amc.2017.07.027, https://doi.org/
10.1016/j.amc.2017.07.027.
[10] A. Kelenc, N. Tratnik and I. G. Yero, Uniquely identifying the edges of a graph: the edge
metric dimension, Discrete Appl. Math. 251 (2018), 204–220, doi:10.1016/j.dam.2018.05.052,
https://doi.org/10.1016/j.dam.2018.05.052.
[11] S. Khuller, B. Raghavachari and A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math.
70 (1996), 217–229, doi:10.1016/0166-218x(95)00106-2, https://doi.org/10.1016/
0166-218x(95)00106-2.
[12] S. Klavžar and M. Tavakoli, Edge metric dimensions via hierarchical product and integer
linear programming, Optim. Lett. 15 (2021), 1993–2003, doi:10.1007/s11590-020-01669-x,
https://doi.org/10.1007/s11590-020-01669-x.
[13] M. Knor, S. Majstorović, A. T. Masa Toshi, R. Škrekovski and I. G. Yero, Graphs with the edge
metric dimension smaller than the metric dimension, Appl. Math. Comput. 401 (2021), 8, doi:
10.1016/j.amc.2021.126076, https://doi.org/10.1016/j.amc.2021.126076.
[14] M. Knor, R. Škrekovski and I. G. Yero, A note on the metric and edge metric dimensions of 2-
connected graphs, Discrete Appl. Math. 319 (2022), 454–460, doi:10.1016/j.dam.2021.02.020,
https://doi.org/10.1016/j.dam.2021.02.020.
[15] D. Kuziak and I. G. Yero, Metric dimension related parameters in graphs: A survey on combi-
natorial, computational and applied results, 2021, arXiv:2107.04877 [math.CO].
[16] L. Laird, R. C. Tillquist, S. Becker and M. E. Lladser, Resolvability of Hamming graphs, SIAM
J. Discrete Math. 34 (2020), 2063–2081, doi:10.1137/19m1274511, https://doi.org/
10.1137/19m1274511.
[17] B. Lindström, On a combinatorial problem in number theory, Canad. Math. Bull.
8 (1965), 477–490, doi:10.4153/cmb-1965-034-2, https://doi.org/10.4153/
cmb-1965-034-2.
[18] N. Nikolić, M. Čangalović and I. Grujičić, Symmetry properties of resolving sets and met-
ric bases in hypercubes, Optim. Lett. 11 (2017), 1057–1067, doi:10.1007/s11590-014-0790-2,
https://doi.org/10.1007/s11590-014-0790-2.
[19] I. Peterin and I. G. Yero, Edge metric dimension of some graph operations, Bull. Malays.
Math. Sci. Soc. 43 (2020), 2465–2477, doi:10.1007/s40840-019-00816-7, https://doi.
org/10.1007/s40840-019-00816-7.
A. Kelenc et al.: On metric dimensions of hypercubes 9
[20] J. Sedlar and R. Škrekovski, Extremal mixed metric dimension with respect to the cyclo-
matic number, Appl. Math. Comput. 404 (2021), Paper No. 126238, 8, doi:10.1016/j.amc.2021.
126238, https://doi.org/10.1016/j.amc.2021.126238.
[21] J. Sedlar and R. Škrekovski, Mixed metric dimension of graphs with edge disjoint cycles, Dis-
crete Appl. Math. 300 (2021), 1–8, doi:10.1016/j.dam.2021.05.004, https://doi.org/
10.1016/j.dam.2021.05.004.
[22] P. J. Slater, Leaves of trees, in: Proceedings of the Sixth Southeastern Conference on Combi-
natorics, Graph Theory, and Computing, 1975 pp. 549–559.
[23] R. C. Tillquist, R. M. Frongillo and M. E. Lladser, Getting the lay of the land in discrete
space: A survey of metric dimension and its applications, 2021, arXiv:2104.07201
[math.CO].
[24] Y. Zhang, L. Hou, B. Hou, W. Wu, D.-Z. Du and S. Gao, On the metric dimension of the
folded n-cube, Optim. Lett. 14 (2020), 249–257, doi:10.1007/s11590-019-01476-z, https:
//doi.org/10.1007/s11590-019-01476-z.