ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 22 (2022) #P3.02 / 387–402
https://doi.org/10.26493/1855-3974.2496.07a
(Also available at http://amc-journal.eu)
The adjacency dimension of graphs*
Sergio Bermudo †
Department of Economics, Quantitative Methods and Economic History,
Pablo de Olavide University, Carretera de Utrera Km. 1, 41013-Sevilla, Spain
José M. Rodrı́guez
Departamento de Matemáticas, Universidad Carlos III de Madrid,
Avenida de la Universidad 30, 28911 Leganés, Madrid, Spain
Juan A. Rodrı́guez-Velázquez
Universitat Rovira i Virgili, Departament d’Enginyeria Informàtica i Matemàtiques,
Av. Paı̈sos Catalans 26, 43007 Tarragona, Spain
José M. Sigarreta
Facultad de Matemáticas, Universidad Autónoma de Guerrero,
Carlos E. Adame No. 54 Col. Garita, 39650 Acalpulco Guerrero, Mexico
Received 1 December 2020, accepted 13 September 2021, published online 9 June 2022
Abstract
It is known that the problem of computing the adjacency dimension of a graph is NP-
hard. This suggests finding the adjacency dimension for special classes of graphs or obtain-
ing good bounds on this invariant. In this work we obtain general bounds on the adjacency
dimension of a graph G in terms of known parameters of G. We discuss the tightness
of these bounds and, for some particular classes of graphs, we obtain closed formulae.
In particular, we show the close relationships that exist between the adjacency dimension
and other parameters, like the domination number, the location-domination number, the
2-domination number, the independent 2-domination number, the vertex cover number, the
independence number and the super domination number.
Keywords: Adjacency dimension, metric dimension, location-domination number, independence num-
ber, super domination number.
Math. Subj. Class. (2020): 05C69, 05C7, 05C12
*This work has been supported in part by three grants from “Ministerio de Economı́a y Competitividad, Agen-
cia Estatal de Investigación (AEI)” and “Fondo Europeo de Desarrollo Regional (FEDER)” (MTM2016-78227-
C2-1-P, MTM2015-70531 and MTM2017-90584-REDT), Spain, and by Junta de Andalucı́a, FEDER-UPO Re-
search and Development Call, reference number UPO-1263769.
†Corresponding author.
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
388 Ars Math. Contemp. 22 (2022) #P3.02 / 387–402
1 Introduction
The metric dimension of a general metric space was introduced in 1953 by Blumenthal [2,
p. 95]. A metric generator for a metric space (X, d) is a set S ⊆ X of points in the
space with the property that every point of X is uniquely determined by the distances from
the elements of S, i.e., S ⊆ X is a metric generator for X if for any pair of distinct
points x, x′ ∈ X there exists s ∈ S such that d(x, s) ̸= d(x′, s). A metric generator of
minimum cardinality in X is called a metric basis, and its cardinality, which is denoted
by dim(X), is called the metric dimension of X . The notion of metric dimension of a
graph was introduced by Slater in [23], where the metric generators were called locating
sets. Harary and Melter [11] independently introduced the same concept, where metric
generators were called resolving sets. Given a simple and connected graph G = (V,E),
we consider the function d : V ×V → N∪{0}, where d(x, y) is the length of a shortest path
in G between u and v and N is the set of positive integers. Since (V, d) is a metric space, a
metric generator for a graph G = (V,E) is simply a metric generator for the metric space
(V, d) and we will use the notation dim(G) instead of dim(V ) for the metric dimension
of G.
Several variations of metric generators have been introduced and studied, namely, re-
solving dominating sets [3], locating-dominating sets [24, 25], independent resolving sets
[5], local metric sets [18], strong resolving sets [22], adjacency generators [15, 16], k-
adjacency generators [6], k-metric generators [1, 7, 8], simultaneous metric generators [21]
etc. In this article, we are interested in the study of adjacency generators.
The notion of adjacency generator was introduced by Jannesari and Omoomi in [16]
as a tool to study the metric dimension of lexicographic product graphs. This concept has
been studied further by Fernau and Rodrı́guez-Velázquez in [9, 10] where they showed that
the (local) metric dimension of the corona product of a graph of order n and some non-
trivial graph H equals n times the (local) adjacency dimension of H . As a consequence
of this strong relation they showed that the problem of computing the adjacency dimension
is NP-hard. This suggests finding the adjacency dimension for special classes of graphs
or obtaining good bounds on this invariant. In this work we obtain general bounds on the
adjacency dimension of a graph G in terms of known parameters of G, while for some
particular cases we obtain closed formulae.
In order to introduce the concept of adjacency generator for a graph G = (V,E), we
define the distance function d2 : V × V → N ∪ {0}, where
d2(x, y) = min{d(x, y), 2}.
An adjacency generator for a graph G = (V,E) is a metric generator for the metric space
(V, d2). Hence, the adjacency dimension of G = (V,E), denoted by adim(G), equals the
metric dimension of (V, d2).
Notice that S ⊆ V is an adjacency generator forG = (V,E) if for every pair of vertices
x, y ∈ V \S there exists s ∈ S which is adjacent to exactly one of these two vertices x and
E-mail addresses: sbernav@upo.es (Sergio Bermudo), jomaro@math.uc3m.es (José M. Rodrı́guez),
juanalberto.rodriguez@urv.cat (Juan A. Rodrı́guez-Velázquez), jsmathguerrero@gmail.com (José M. Sigarreta)
S. Bermudo et al.: The adjacency dimension of graphs 389
y. Therefore, S is an adjacency generator for G if and only if S is an adjacency generator
for its complement G. Consequently,
adim(G) = adim(G). (1.1)
From the definition of adjacency and metric bases, we deduce that S is an adjacency basis
of a graph G of diameter at most two if and only if S is a metric basis of G. In these cases,
adim(G) = dim(G). The reader is referred to [6, 10, 15, 16, 20] for known results on the
adjacency dimension.
The paper is organized as follows. Section 2 is devoted to study the variation of the
adjacency dimension of a graph by removing a set of edges. In particular, we wonder how
far can decrease the adjacency dimension by removing edges from a complete graph and
we obtain a lower bound on the adjacency dimension of any graph in terms of the order.
In Section 3 we show the close relationships that exist between the adjacency dimension
and other parameters, like the domination number, the location-domination number, the
2-domination number, the independent 2-domination number, the vertex cover number, the
independence number and the super domination number.
We will use the notation Kn, Kr,n−r, Cn, Pn and Nn for complete graphs, complete
bipartite graphs, cycle graphs, path graphs and empty graphs of order n, respectively. We
use the notation u ∼ v if u and v are adjacent vertices and G ∼= H if G and H are isomor-
phic graphs. For a vertex v of a graph G, N(v) will denote the set of neighbours or open
neighborhood of v in G, i.e., N(v) = {u ∈ V (G) : u ∼ v}. The closed neighborhood,
denoted by N [v], equals N(v) ∪ {v}. We also define deg(v) = |N(v)| as the degree of
v ∈ V (G), as well as, δ = minv∈V (G){deg(v)} and ∆ = maxv∈V (G){deg(v)}. For the
remainder of the paper, definitions will be introduced whenever a concept is needed.
2 The effect of removing edges and bounds in terms of the order
The following theorem is an important tool to derive some of our results.
Theorem 2.1 ([16]). Let G be a graph of order n. Then the following statements hold.
(i) adim(G) = 1 if and only if n ∈ {1, 2, 3}, G ̸∼= K3 and G ̸∼= N3.
(ii) adim(G) = n− 1 if and only if G ∼= Kn or G ∼= Nn.
(iii) If n ≥ 3 and t ∈ {1, . . . , n− 1}, then adim(Kt,n−t) = n− 2.
(iv) If n ≥ 4, then adim(Pn) = adim(Cn) =
⌊
2n+2
5
⌋
.
In this section we show the effect, on the adjacency dimension, of an operation which
removes a set of edges from a graph. Given a non-empty graph G = (V,E) and an edge
e ∈ E we denote by G− e = (V,E \ {e}) the subgraph obtained by removing the edge e
from G. In general, given a set of edges Ek = {e1, . . . , ek} ⊆ E we denote by G− Ek =
(V,E \Ek) the subgraph obtained by removing the k edges in Ek from G. By analogy we
define the supergraphs G+ e = (V,E ∪ {e}) and G+ Ek = (V,E ∪ Ek), where {e} and
Ek are sets of edges of the complement of G.
Theorem 2.2. LetG = (V,E) be a non-empty graph. For any setEk = {e1, . . . , ek} ⊆ E,
adim(G)− k ≤ adim(G− Ek) ≤ adim(G) + k.
390 Ars Math. Contemp. 22 (2022) #P3.02 / 387–402
Proof. Since (G− Ek−1)− ek = G− Ek, it is enough to prove that, for any e ∈ E,
adim(G)− 1 ≤ adim(G− e) ≤ adim(G) + 1.
Let S be an adjacency basis of G − e, where e = xy. Since S ∪ {y} is an adjacency
generator forG, we have that adim(G) ≤ |S∪{y}| ≤ |S|+1 = adim(G−e)+1. Hence,
adim(G)− 1 ≤ adim(G− e).
Finally, let us observe that adim(G − e) = adim(G− e) = adim(G + e) ≤
adim((G+e)−e)+1 = adim(G)+1 = adim(G)+1. Therefore, the result follows.
Since adim(G − Ek) = adim(G− Ek) = adim(G + Ek), we conclude that
adim(G − Ek) = adim(G) − k if and only if the graph H = G + Ek satisfies
adim(H − Ek) = adim(H) + k. Therefore, in order to show that the inequalities above
are tight, we only need to consider one of them. For instance, adim(Kn − e) = n − 2 =
adim(Kn) − 1. With the aim of showing a more general example, let us consider s stars
Hi ∼= K1,r, r ≥ 4, such that vi is the center and ui1 , . . . , uir are the leaves of Hi, for
i ∈ {1, . . . , s}. Let ei = ui1ui2 , Gi = Hi + ei and M = {vivi+1 : 1 ≤ i < s}, and
define Gr,s = (V,E), where V =
⋃s
i=1 V (Gi) and E = (
⋃s
i=1E(Gi)) ∪M . It is read-
ily seen that adim(Gr,s) = s(r − 1) − 1, while for any k ≤ s and Ek = {e1, . . . , ek},
adim(Gr,s − Ek) = s(r − 1)− 1 + k = adim(Gr,s) + k.
Figure 1: The set of black-colored vertices is an adjacency basis of G4,3.
Figure 2: The set of black-colored vertices is an adjacency basis of G4,3 − E2.
Figure 1 shows the graph G4,3, while Figure 2 shows the graph G4,3−E2. In this case,
adim(G4,3 − E2) = 10 = adim(G4,3) + 2.
All graphs of order n are obtained by successive elimination of edges from a complete
graph (or by successive addition of edges to an empty graph). We know from Theorem 2.1
that for any graph G of order n, adim(G) ≤ n − 1 and the equality holds if and only if
G ∼= Kn or G ∼= Nn. Hence, by Theorem 2.2 we conclude that adim(Kn − e) = n − 2
for every e ∈ E(Kn). Now we wonder how far can decrease the adjacency dimension
by removing edges from Kn, i.e., which is the lower bound for the adjacency dimension
in terms of the order of the graph. This problem is addressed in Propositions 2.3 and 2.4.
Before stating it we need to introduce the following notation.
Given a positive integer s, let G′ be the family of all graphs of order s and G′′ the
family of all graphs of order 2s. We can assume that the graphs in G′ are defined on
S. Bermudo et al.: The adjacency dimension of graphs 391
x1 x3
x2
111
222
122
112
212
121
211
221
Figure 3: A graph G ∈ G3 constructed from G′ ∼= N3 ∈ G′ and G′′ ∼= (K2 ∪N6) ∈ G′′.
S = {x1, . . . , xs} and the graphs in G′′ are defined on the set {1, 2}s of binary words of
length s. Let Gs be the family of graphs constructed from G′ and G′′ as follows. We say that
G ∈ Gs if and only if there exist G′ ∈ G′ and G′′ ∈ G′′ such that V (G) = V (G′)∪ V (G′′)
and E(G) = E(G′)∪E(G′′)∪E∗, where E∗ is the set of edges connecting vertices of G′
with vertices of G′′ in such a way that xi is adjacent to y ∈ {1, 2}s if and only if the i-th
letter of y is 1. Notice that S is an adjacency generator for every G ∈ Gs. Figure 3 shows
a graph G ∈ G3 constructed from G′ ∼= N3 ∈ G′ and G′′ ∼= (K2 ∪N6) ∈ G′′.
The following inequality appeared recently in [15], but we characterize here all graphs
satisfying the equality.
Proposition 2.3. For any graph G of order n,
2adim(G) + adim(G) ≥ n. (2.1)
Furthermore, a graph G of order n = 2s + s satisfies adim(G) = s if and only if G ∈ Gs.
Proof. As we mentioned before, the inequality was proved in [15]. By definition of Gs, if
G ∈ Gs, then {x1, . . . , xs} is an adjacency generator. Now, if adim(G) = r < s, then
Equation (2.1) leads to n = s + 2s > r + 2r ≥ n, which is a contradiction. Therefore,
G ∈ Gs leads to adim(G) = s.
Conversely, suppose that G has order n = 2s + s and adim(G) = s. In this case, for
any adjacency basis S = {x1, . . . , xs} ofG, the function ψ : V (G)\S −→ {1, 2}s defined
by
ψ(x) = (d2(x, x1), . . . , d2(x, xs)),
is bijective, as it is injective and |V (G)\S| = 2s. Hence, takingG′ ∈ G′ as the subgraph of
G induced by S, G′′ ∈ G′′ as the subgraph of G induced by V (G) \ S and E∗ as the set of
edges connecting vertices in S with vertices in V (G)\S, we can conclude thatG ∈ Gs.
Proposition 2.4. For any graph G of order n, adim(G) ≥
⌈
ln( 2n3 )
ln(2)
⌉
.
Proof. If G is a graph with order n and adim(G) = k, since
n ≤ 2k + k ≤ 2k + 2k−1 = 2k
(
1 +
1
2
)
= 2k
(
3
2
)
,
we conclude that k ≥ ln(
2n
3 )
ln(2) .
392 Ars Math. Contemp. 22 (2022) #P3.02 / 387–402
The bound above is tight. It is achieved, for instance, for the family Gs of graphs
constructed prior to Proposition 2.3. These graphs have order n = s + 2s and metric
dimension s. To check the tightness of the bound we only need to observe that 2(s+2
s)
3 >
2s−1, for every positive integer s. Examples of graphs of small order for which the bound
is achieved are the path P3, the cycles Cr (4 ≤ r ≤ 6), and the cube Q3 = K2□K2□K2,
as adim(P3) = 1, adim(C4) = adim(C5) = adim(C6) = 2 and adim(Q3) = 3.
By Theorem 2.1, for any non-complete and non-empty graph of order n, adim(G) ≤
n − 2. The characterization for graphs G such that adim(G) = n − 2 appeared recently
in [15].
Theorem 2.5. Let G be a connected graph of order n ≥ 5. Then adim(G) = n− 2 if and
only if one of the following conditions holds.
(i) G ∼= Kt,n−t, for some t ∈ {1, . . . , n− 1}.
(ii) G ∼= Kn−t +Nt, for some t ∈ {2, . . . , n− 2}.
(iii) G ∼= (K1 ∪Kt) +Kn−t−1, for some t ∈ {2, . . . , n− 2}.
We conclude this section with a characterization of all graphs G satisfying that
adim(G) = 2, which also appeared in [15].
Theorem 2.6. Let G be a connected graph of order n. Then adim(G) = 2 if and only if
one of the following conditions holds for G (or G).
(a) G ∼= K3.
(b) n = 4 and G ̸∼= K4.
(c) n = 5 and G ̸∼= K5, G ̸∼= Kt,5−t for t ∈ {1, . . . , 4}, G ̸∼= K5−t + Nt and
G ̸∼= (K1 ∪Kt) +K4−t for t ∈ {2, 3}.
(d) n = 6 and G ∈ G2.
3 Relationship between the adjacency dimension and other parame-
ters
A setD ⊆ V (G) is a dominating set ofG ifN(x)∩D ̸= ∅ for every vertex x ∈ V (G)\D.
The domination number, γ(G), is the minimum cardinality among all dominating sets of
G. A dominating set of cardinality γ(G) is called a γ(G)-set. The reader is referred to the
books [12, 13] on the domination theory.
The following result is immediate from Equation (1.1) and the fact that at most one
vertex of G is not dominated by the vertices in an adjacency generator of G.
Remark 3.1 ([10]). For any graph G,
adim(G) ≥ max{γ(G), γ(G)} − 1.
The bound above is tight. For instance, it is attained by the corona graphs Kr ⊙ K1,
r ≥ 3, as adim(Kr ⊙K1) = r − 1 and γ(Kr ⊙K1) = r. Another example is any graph
G ∈ G with γ(G) = s+ 1. A particular case is shown in Figure 3.
S. Bermudo et al.: The adjacency dimension of graphs 393
A locating-dominating set is a dominating set D that locates/distinguishes all the ver-
tices in the sense that every vertex not in D is uniquely determined by its neighbourhood
in D, i.e., N(u) ∩ D ̸= N(v) ∩ D for every pair of vertices u, v ∈ V (G) \ D. The
location-domination number of G, denoted λ(G), is the minimum cardinality among all
locating-dominating sets in G. A locating-dominating set of cardinality λ(G) is called a
λ(G)-set. The concept of a locating-dominating set was introduced and first studied by
Slater [24, 25] and studied, for instance, in [4, 14, 19] and elsewhere.
Since every locating-dominating set is an adjacency generator and any adjacency basis
S dominates at least all but one vertex in V (G) \ S, we deduce the following remark.
Remark 3.2. For any graph G,
adim(G) ≤ λ(G) ≤ adim(G) + 1.
Furthermore, λ(G) = adim(G) + 1 if and only if no adjacency basis of G is a dominating
set.
In general, for non-connected graphs we can state the following remark.
Remark 3.3. Let {G1, . . . , Gk} be the set of components of a graph G. If there exists at
least one component where no adjacency basis is a dominating set, then
adim(G) = −1 +
k∑
i=1
λ(Gi).
Otherwise,
adim(G) =
k∑
i=1
λ(Gi) =
k∑
i=1
adim(Gi).
Furthermore, if there are exactly t ≥ 1 components where no adjacency basis is a dominat-
ing set, then
adim(G) = t− 1 +
k∑
i=1
adim(Gi).
According to the two remarks above, tight bounds on adim(G) impose good bounds
on λ(G). In any case, the problem of obtaining the location-domination number of a graph
G from the adjacency dimension of G, forces us to know whether G has dominating basis
or not. Therefore, we can state the following open problem.
Problem 3.4. Characterize the graphs where no adjacency basis is a dominating set.
In order to show some families of graphs where every adjacency basis is a dominating
set, we proceed to state the following lemma obtained previously in [20].
Lemma 3.5 ([20]). Let G be a connected graph. If has diameter D ≥ 6, or G ∼= Cn with
n ≥ 7, or G is a graph of girth g ≥ 5 and minimum degree δ ≥ 3, then for every adjacency
generator B for G and every v ∈ V (G), B ̸⊆ N(v).
Theorem 3.6. Let G be a connected graph. If G has diameter D ≥ 6, or G ∼= Cn with
n ≥ 7, or G is a graph of girth g ≥ 5 and minimum degree δ ≥ 3, then
adim(G) = λ(G).
394 Ars Math. Contemp. 22 (2022) #P3.02 / 387–402
Proof. Let G be a graph satisfying the hypothesis and let S be an adjacency basis of G. By
Lemma 3.5 we deduce that S is a dominating set of G and, since S is an adjacency basis of
G, we can conclude that S is a locating-dominating set ofG. Therefore, adim(G) = λ(G),
as required.
Theorem 3.7. Let G be a graph of order n and maximum degree ∆. If ∆ ln(2) < ln
(
2n
3
)
,
then adim(G) = λ(G).
Proof. Let S be an adjacency basis of G. If ∆ ln(2) < ln
(
2n
3
)
, then Proposition 2.4 leads
to deg(u) ≤ ∆ < ln(
2n
3 )
ln(2) ≤ |S| for every u ∈ V (G) \ S, concluding that S is a locating-
dominating set of G. Therefore, adim(G) = λ(G).
The following result is a direct consequence of the theorem above.
Corollary 3.8. LetG be a graph of order n and minimum degree δ. If δ > n−
⌈
ln( 2n3 )
ln(2)
⌉
−1,
then adim(G) = λ(G).
Theorem 3.9. Given a graph G of order n, the following assertions hold.
(i) If G has at most one isolated vertex, then adim(G) ≤ n− γ(G).
(ii) If G has at most one vertex of degree n− 1, then adim(G) ≤ n− γ(G).
(iii) If G has no isolated vertices, then λ(G) ≤ n− γ(G).
Proof. In this proof, the number of edges of a graph H will be denoted by m(H). Let
G be a graph having at most one isolated vertex and let S be a γ(G)-set such that for any
γ(G)-set S′ it is satisfiedm(⟨S⟩) ≥ m(⟨S′⟩). We shall show that V (G)\S is an adjacency
generator. Suppose to the contrary that V (G) \ S is not an adjacency generator. In such
a case, there exist x, y ∈ S such that for every z ∈ V (G) \ S, either x, y ∈ N(z) or
x, y /∈ N(z). As a result, neither x nor y has any private neighbour (with respect to S) in
V (G) \ S. We can assume that x is not an isolated vertex. Now, if N(x) ∩ S ̸= ∅, then
S \ {x} is a dominating set, which is a contradiction. If N(x) ∩ S = ∅, then taking any
z ∈ N(x) we have that S′ = (S \ {x}) ∪ {z} is a γ(G)-set such that m(⟨S′⟩) > m(⟨S⟩),
which is a contradiction. Therefore, V (G) \ S is an adjacency generator, and so (i) and (ii)
follow.
Furthermore, if G has no isolated vertices, then the complement of every γ(G)-set is a
dominating set, which implies that V (G) \ S is a locating-dominating set. Therefore, (iii)
follows.
The bounds above are tight. For instance, bounds (i) and (iii) are achieved by G ∼= Kn,
G ∼= P4 and Kp,q (2 ≤ p ≤ q). Bound (i) is also achieved by G ∼= K1 ∪Kr (r ≥ 2), as
adim(K1 ∪ Kr) = r − 1 and γ(K1 ∪ Kr) = 2, and (iii) is also achieved by any corona
graph G ∼= H ⊙K1, as in this case λ(G) = |V (H)| = γ(G) = n2 . Obviously, bound (i) is
achieved by a graph G if and only if bound (ii) is achieved by G.
We now emphasize two well-known bounds on the domination number.
Theorem 3.10 ([26]). For any graph G of order n and maximum degree ∆ ≥ 1,
γ(G) ≥
⌈
n
∆+ 1
⌉
.
S. Bermudo et al.: The adjacency dimension of graphs 395
A graph invariant closely related to the domination number is the 2-packing number. A
set S ⊆ V (G) is a 2-packing if for each pair of vertices u, v ∈ S, N [u] ∩N [v] = ∅. The
2-packing number ρ(G) is the cardinality of a maximum 2-packing.
Theorem 3.11 ([13]). For any graph G,
γ(G) ≥ ρ(G).
The following result is a direct consequence of combining Remark 3.1 and Theo-
rems 3.9, 3.10 and 3.11.
Theorem 3.12. Let G be a non-empty graph of order n, maximum degree ∆ and minimum
degree δ. The following assertions hold.
(a) adim(G) ≥ max
{⌈
δ
n−δ
⌉
,
⌈
n−∆−1
∆+1
⌉}
.
(b) adim(G) ≥ max{ρ(G), ρ(G)} − 1.
(c) If δ ≥ 1, then λ(G) ≤ n−max
{
ρ(G),
⌈
n
∆+1
⌉}
.
(d) If G has at most one isolated vertex, then adim(G) ≤ n−max
{
ρ(G),
⌈
n
∆+1
⌉}
.
(e) If G has at most one vertex of degree n− 1, then
adim(G) ≤ n−max
{
ρ(G),
⌈
n
n− δ
⌉}
.
Bound (a) is achieved by complete graphs, while bounds (b) and (c) are achieved by the
corona graphsKr⊙K1, r ≥ 3, as in this case adim(Kr⊙K1) = r−1 and ρ(Kr⊙K1) =
r = λ(Kr ⊙K1). Bounds (c) and (d) are achieved by G = Kn. Obviously, bound (e) is
achieved by a graph G is and only if bound (d) is achieved by G.
A set S ⊆ V (G) is a k-dominating set if |N(v) ∩ S| ≥ k for every v ∈ V (G) \ S.
The minimum cardinality among all k-dominating sets is called the k-domination number
of G and it is denoted by γk(G). A set S ⊆ V (G) is an independent k-dominating set if
it is both an independent set and a k-dominating set. The minimum cardinality among all
independent k-dominating sets is called the independent k-domination number of G and it
is denoted by ik(G).
Theorem 3.13. If G is a non-trivial graph which does not have cycles of length four, then
λ(G) ≤ γ2(G).
Proof. Let S be a 2-dominating set. If S is not an adjacency basis, then there exist u, v ∈
V \ S such that N(u) ∩ S = N(v) ∩ S. Since |N(v) ∩ S| ≥ 2, there exists a cycle with
four vertices, which is a contradiction.
The inequality above is tight. For instance, for the graph shown in Figure 4 we have
that adim(G) = λ(G) = γ2(G) = 4.
Theorem 3.14. Let G be a graph which does not have cycles of length four, and let S be a
γ2(G)-set. If there exists s ∈ S such that N [s] ∩ S ̸= N(x) ∩ S for every x ∈ N(s) \ S,
then adim(G) ≤ γ2(G)− 1.
396 Ars Math. Contemp. 22 (2022) #P3.02 / 387–402
Figure 4: The set of black-colored vertices is an adjacency basis and a 2-dominating set.
Hence, adim(G) = λ(G) = γ2(G) = 4.
Proof. Let s ∈ S such that N [s] ∩ S ̸= N(x) ∩ S for every x ∈ N(s) \ S. Let us see that
S′ = S \{s} is an adjacency generator. Suppose to the contrary, that S′ is not an adjacency
generator. In such a case, there exist u, v ∈ V (G) \ S′ such that N(u) ∩ S′ = N(v) ∩ S′.
We differentiate three cases for these two vertices.
Case 1: u = s. In this case v ̸∈ N(s) and so |N(v) ∩ S′| ≥ 2. Hence, there exists a cycle
with four vertices, which is a contradiction.
Case 2: u ̸∈ N [s]. Since |N(u) ∩ S′| ≥ 2, there exists a cycle with four vertices, which is
a contradiction.
Case 3: u, v ∈ N(s). Since |N(u) ∩ S| ≥ 2, there exists a cycle with four vertices, which
is a contradiction.
Therefore, the result follows.
In the next result we are assuming that any acyclic graph has girth g = +∞.
Corollary 3.15. LetG be a graph of minimum degree δ ≥ 1. Then the following assertions
hold.
(i) If G has girth g ≥ 5, then adim(G) ≤ γ2(G)− 1.
(ii) If G has an independent 2-dominating set and does not have cycles of length four,
then adim(G) ≤ i2(G)− 1.
The bounds above are tight. For instance, for 3 ≤ k ≤ 7 we have that i2(C2k) =
γ2(C2k) = k and adim(C2k) = k − 1.
Recall that a set S of vertices of G is a vertex cover of G if every edge of G is incident
with at least one vertex of S. The vertex cover number of G, denoted by β(G), is the
smallest cardinality of a vertex cover of G. We refer to a β(G)-set in a graph G as a vertex
cover of cardinality β(G). The largest cardinality of a set of vertices of G, no two of
which are adjacent, is called the independence number of G and it is denoted by α(G).
The following well-known result, due to Gallai, states the relationship between the
independence number and the vertex cover number of a graph.
Theorem 3.16. (Gallai’s theorem) For any graph G of order n,
α(G) + β(G) = n.
A leaf is a vertex of degree one and a strong support vertex is a vertex which is adjacent
to more than one leaf.
Theorem 3.17. Let G be a graph of order n without isolated vertices. If G does not have
neither cycles of four vertices nor strong support vertices, then
λ(G) ≤ β(G) = n− α(G).
S. Bermudo et al.: The adjacency dimension of graphs 397
Proof. Let S be a β(G)-set. Since V (G) \ S is an independent set and G does not have
isolated vertices, S is a dominating set. Suppose to the contrary that S is not an adjacency
generator. In such a case, there exist u, v ∈ V (G) \ S such that N(u) ∩ S = N(v) ∩ S. If
|N(v)∩S| ≥ 2, then there exists a cycle with four vertices, which is a contradiction. Now,
if |N(v) ∩ S| = {w}, then w is a strong support vertex, which is a contradiction again.
Therefore, the results follows.
To see that the above inequality is tight, we can consider the graph shown in Figure 4. In
this case, the set of black-colored vertices is a β(G)-set and adim(G) = λ(G) = β(G) =
n− α(G) = 4.
A set S ⊆ V (G) is called a super dominating set ofG if for every vertex u ∈ V (G)\S,
there exists u′ ∈ S such thatN(u′)\S = {u}. The super domination number ofG, denoted
by γsp(G), is the minimum cardinality among all super dominating sets in G. A super
dominating set of cardinality γsp(G) is called a γsp(G)-set. The study of super domination
in graphs was introduced in [17].
Theorem 3.18. For any graph G,
λ(G) ≤ γsp(G).
Furthermore, if G has minimum degree δ ≥ 3 and does not have cycles of length four, then
λ(G) ≤ γsp(G)− 1.
Proof. Let S be a γsp(G)-set, C = V (G) \ S and the function f : C −→ S where f(u)
is one of the vertices in S satisfying that N(f(u)) \ S = {u}. Since, f(u) distinguishes
u ∈ C from any v ∈ C \{u}, we conclude that S is a locating-dominating set ofG. Hence,
λ(G) ≤ |S| = γsp(G).
Assume that G has minimum degree δ ≥ 3 and does not have cycles of length four. Let
A = f(C) be the image of f and B = S \A. We differentiate the following two cases.
Case 1: There exists u ∈ C such that N(u) ∩ B ̸= ∅. We claim that S′ = S \ {f(u)} is
a locating-dominating set. Since N(f(u)) ∩ C = {u} and deg(f(u)) ≥ 3, we have that
|N(f(u)) ∩ S′| ≥ 2. Hence, S′ is a dominating set. Now, every v ∈ C \ {u}
is distinguished from u by f(v) ∈ S′. Finally, if f(u) and v ∈ C are not distinguished
by some vertex in S′, then v, f(u) and two vertices belonging to N(f(u)) ∩ S′ form a
cycle of length four, which is a contradiction. Therefore, S′ is a locating-dominating set,
and so λ(G) ≤ |S′| = γsp(G)− 1.
Case 2: N(u) ∩B = ∅ for every u ∈ C. Notice that |N(f(u)) ∩ S| ≥ 2 for every u ∈ C.
Let u, v ∈ C be two adjacent vertices. We claim that S′ = (S \ {f(u), f(v)}) ∪ {v}
is a locating-dominating set. Obviously, S′ is a dominating set. Now, u is distinguished
from any u′ ∈ C \ {u, v} by f(u′) ∈ S′, and v distinguishes f(u) from f(v). Notice
also that if x ∈ C \ {u, v}, then |N(x) ∩ (S′ \ {v})| = 1 and, since u ∼ v, we have that
f(u) ̸∼ f(v), which implies that |N(y) ∩ (S′ \ {v})| ≥ 2 for every y ∈ {f(u), f(v)}.
Thus, if x ∈ C \ {v} and y ∈ {f(u), f(v)}, then N(x)∩S′ ̸= N(y)∩S′. In summary, S′
is a locating-dominating set and, as a result, λ(G) ≤ |S′| = γsp(G)− 1.
To show that the inequality λ(G) ≤ γsp(G) is tight we consider the following cases:
λ(Kn) = γsp(Kn) = n − 1, λ(K1,n−1) = γsp(K1,n−1) = n − 1, λ(Kr,n−r) =
γsp(Kr,n−r) = n− 2 for 2 ≤ r ≤ n− 2 and λ(H ⊙Nt) = γsp(H ⊙Nt) = |V (H)|t. For
the Petersen graph, shown in Figure 5, we have that λ(G) = γsp(G)− 1 = 3.
398 Ars Math. Contemp. 22 (2022) #P3.02 / 387–402
Figure 5: This figure shows three copies of the Petersen graph. The set of black-coloured
vertices, on the left forms an adjacency basis, on the center forms a λ(G)-set, while on the
right forms a γsp(G)-set.
Lemma 3.19. Let G be a graph with two adjacent vertices x, y ∈ V (G) such that
deg(x) = 1 and deg(y) = 2. If G′ = G − {x, y}, then adim(G) ≤ adim(G′) + 1
and γsp(G) = γsp(G′) + 1.
Proof. If S is an adjacency basis ofG′, then S∪{x} is an adjacency generator ofG, which
implies that adim(G) ≤ adim(G′) + 1.
Assume that D′ is a γsp(G′)-set and u ∈ V (G′) is adjacent to y in G. If u ∈ D′,
then D′ ∪ {y} is a super dominating set of G, while if u /∈ D′, then D′ ∪ {x} is a super
dominating set of G. Therefore, γsp(G) ≤ γsp(G′) + 1. Now, let D be a γsp(G)-set and
v ∈ N(y) \ {x}. If x, y ∈ D, then v /∈ D and (D ∪ {v}) \ {x, y} is a super dominating set
of G′, which implies that γsp(G′) ≤ γsp(G)− 1. Now, if |D ∩ {x, y}| = 1, D \ {x, y} is
a super dominating set of G′ and so γsp(G′) ≤ γsp(G)− 1.
We know that adim(P4) = λ(P4) = γsp(P4) = 2, adim(Kn) = λ(Kn) = γsp(Kn) =
n− 1, adim(Kp,q) = λ(Kp,q) = γsp(Kp,q) = p+ q− 2 (2 ≤ p ≤ q). We proceed to show
that for the remaining graphs, adim(G) ≤ γsp(G)− 1.
Theorem 3.20. For any connected graph G /∈ {P4,Kn,Kp,q}, with 2 ≤ p ≤ q,
adim(G) ≤ γsp(G)− 1.
Proof of Theorem 3.20. Let G be a connected graph such that G /∈ {P4,Kn,Kp,q} for
2 ≤ p ≤ q. If G′ = G − {x, y}, where deg(x) = 1 and deg(y) = 2, then we have the
following:
S. Bermudo et al.: The adjacency dimension of graphs 399
• If G′ ∼= P4, then adim(G) = 2 < 3 = γsp(G).
• If G′ ∼= K1, then adim(G) = 1 < 2 = γsp(G).
• If G′ ∼= Kn−2 (n ≥ 5), then adim(G) = n− 3 < n− 2 = γsp(G).
• If G′ ∼= Kp,q (2 ≤ p ≤ q), then adim(G) = p+ q − 2 < p+ q − 1 = γsp(G).
Hence, by Lemma 3.19 we only need to consider the case where G does not have vertices
of degree one which are adjacent to vertices of degree two.
Let D be a γsp(G)-set, C = V (G) \D and f : C −→ D a function such that, for every
u ∈ C, f(u) is one of the vertices in S satisfying that N(f(u)) \ S = {u}. Let A = f(C)
be the image of f and B = S \ A. Notice that Dc = C ∪ B is also a γsp(G)-set, so any
condition given on A could be also considered on C.
Suppose to the contrary that adim(G) ≥ γsp(G). With the assumptions above in mind,
we proceed to prove the following eight claims.
Claim 1. For any vertex x ∈ C, |N(x) ∩ C| ≤ 1 and |N(f(x)) ∩A| ≤ 1.
Proof of Claim 1. If there exist y, z ∈ C such that f(y), f(z) ∈ N(f(x)) ∩A, then x and
f(x) are distinguished by f(y); x and any u ∈ C \ {x} are distinguished by f(u); while
f(x) and any u ∈ C \ {x} are distinguished by f(y) or by f(z). Hence, D \ {f(x)} is an
adjacency generator, which is a contradiction.
If |N(x) ∩ C| ≤ 1, then we proceed by analogy to the proof above using Dc instead
of D.
Claim 2. For any vertex x ∈ C, deg(x) ≥ 2 and deg(f(x)) ≥ 2.
Proof of Claim 2. Suppose that there exists x ∈ C such that deg(x) = 1. If N(f(x)) ∩
B = ∅, then (by the connectivity of G) Claim 1 leads to deg(f(x)) = 2, which is a
contradiction with our assumptions. Now, if there exists v ∈ N(f(x)) ∩B, then f(x) and
x are distinguished by v; for any y ∈ C \ {x}, f(y) and f(x) are distinguished by y; while
f(y) and x are distinguished by y. Thus, Dc \ {x} is an adjacency generator, which is a
contradiction.
If deg(f(x)) = 1, then we proceed by analogy to the proof above using D instead of
Dc.
Claim 3. Let x ∈ C. IfN(x)∩C = ∅ orN(f(x))∩A = ∅, thenN(x)∩B = N(f(x))∩B.
Proof of Claim 3. If N(f(x)) ∩ A = ∅, then for any z ∈ C \ {x}, f(x) and z are distin-
guished by f(z). SinceD\{f(x)} is not an adjacency generator,N(f(x))∩B = N(x)∩B.
A similar argument works for the case N(x) ∩ C = ∅.
Claim 4. Let x, y ∈ C. If N(f(x)) ∩ A = {f(y)}, then N(f(x)) ∩ B = N(y) ∩ B and
N(f(y)) ∩B = N(x) ∩B.
Proof of Claim 4. Since D \ {f(x)} is not an adjacency generator, if N(f(x)) ∩ A =
{f(y)}, thenN(f(x))∩B = N(y)∩B. Furthermore, by Claim 1,N(f(x))∩A = {f(y)}
leads to N(f(y)) ∩ A = {f(x)}, and since D \ {f(y)} is not an adjacency generator, we
have that N(f(y)) ∩B = N(x) ∩B.
Claim 5. If v ∈ B, then |N(v) ∩A| = 1 and |N(v) ∩ C| = 1.
400 Ars Math. Contemp. 22 (2022) #P3.02 / 387–402
Proof of Claim 5. If v ∈ B and N(v) ∩ A = ∅, then v and any x ∈ C are distinguished
by f(x). Now, if v ∈ B and and there exist y, z ∈ C such that f(y), f(z) ∈ N(v) ∩ A,
then v and any x ∈ C are distinguished by f(y) or by f(z). In both cases, D \ {v} is an
adjacency generator, which is a contradiction. Therefore, |N(v) ∩A| = 1. By analogy we
deduce that |N(v) ∩ C| = 1.
Claim 6. If v1, v2 ∈ B are adjacent vertices, N(v1)∩A = {f(x)} and N(v1)∩C = {y},
then N(v2) ∩A = {f(y)} and N(v2) ∩ C = {x}.
Proof of Claim 6. Assume that v1, v2 ∈ B are adjacent vertices, N(v1)∩A = {f(x)} and
N(v1)∩C = {y}. Since D \ {v1} is not an adjacency generator and f(x) distinguishes v1
and z for every z ∈ C\{x}, we have that x ∈ N(v2). Thus, by Claim 5,N(v2)∩C = {x}.
Furthermore, since D \ {v2} is not an adjacency generator and v1 distinguishes v2 and z
for every z ∈ C \ {y}, we have that f(y) ∈ N(v2). Hence, by Claim 5 we conclude that
N(v2) ∩A = {f(y)}.
Claim 7. If there exists x ∈ C such that N(x) ∩ C = ∅ and N(f(x)) ∩ A = ∅, then
|C| = 1 and G is a complete graph.
Proof of Claim 7. Assume that there exists a vertex x ∈ C such that N(x) ∩ C = ∅ and
N(f(x)) ∩ A = ∅. By Claim 3, N(x) ∩ B = N(f(x)) ∩ B. Let Bx = N(x) ∩ B,
which is nonempty, as G is connected and G ̸∼= K2. If there exist two nonadjacent vertices
vr, vs ∈ Bx, thenD\{vs} is an adjacency generator because x and vs are distinguished by
vr, and any u ∈ C \{x} is distinguished from vs by f(u). Therefore, X = {x, f(x)}∪Bx
induces a complete graph. Now, by the connectivity of G, if V (G) ̸= X , then there
exist two adjacent vertices b, b′ ∈ B such that b ∈ Bx and b′ ∈ B \ Bx. In such a case,
applying Claim 6 for x = y, we conclude that b′ ∈ Bx, which is a contradiction. Therefore,
V (G) = X , |C| = 1 and G is a complete graph.
Claim 8. If there exist x, y ∈ C such that N(f(x)) ∩A = {f(y)}, then G ∼= Kp,q , where
2 ≤ p ≤ q.
Proof of Claim 8. We differentiate two cases.
Case 1: N(x) ∩ C = {y}. Since the subgraph induced by U = {x, f(x), y, f(y)} is
isomorphic to K2,2, V (G) \ U ̸= ∅. By Claims 1, 4 and 5, every vertex in V (G) \ U
which is adjacent to some vertex in U has to belong to B1 = B ∩ N(f(x)) ∩ N(y) or to
B2 = B ∩ N(x) ∩ N(f(y)). Notice that B1 ∩ B2 = ∅. Let X1 = {x, f(y)} ∪ B1 and
X2 = {f(x), y}∪B2. Let us see that G is a complete bipartite graph. Firstly, if there exist
two adjacent vertices u ∈ V (G) \ (X1 ∪ X2) and v ∈ B1 ∪ B2, by the definition of B1
and B2, we know that u ̸∈ A ∪ C. Hence, if v belongs, for instance, to B1, by Claim 6,
u ∈ B2, which is a contradiction. Consequently, V (G) = X1 ∪ X2. Secondly, if there
exist two adjacent vertices u, v ∈ B, by Claim 6, either u ∈ B1 and v ∈ B2 or u ∈ B2 and
v ∈ B1. Finally, if there exist two nonadjacent vertices u ∈ B1 and v ∈ B2, since u and x
are distinguished by v, while u and any z ∈ C \{x} are distinguished by f(z), we have that
D \ {u} is an adjacency generator, which is a contradiction. Therefore, G = (X1 ∪X2, E)
is a complete bipartite graph with |X1| ≥ 2 and |X2| ≥ 2.
Case 2: For any x, y ∈ C such that N(f(x)) ∩ A = {f(y)}, the subgraph induced by
{x, f(x), y, f(y)} is not isomorphic to K2,2. By Claim 2, for every x ∈ C, deg(x) ≥ 2
S. Bermudo et al.: The adjacency dimension of graphs 401
and deg(f(x)) ≥ 2. Since adim(Cn) =
⌊
2n+2
5
⌋
for n ≥ 4 and γsp(Cn) =
⌈
n
2
⌉
for n ≥ 3,
we have that adim(Cn) ≤ γsp(Cn) − 1 for any n ≥ 5. Hence, G ̸∼= Cn and so B ̸= ∅.
By Claim 7, for every x ∈ C either N(x) ∩ C ̸= ∅ or N(f(x)) ∩ A ̸= ∅. Suppose that
there exist x, y ∈ C such that y /∈ N(x) and N(f(x)) ∩ A = {f(y)}. If there exists
b ∈ B ∩ N(x) ∩ N(f(y)), then D′ = (D ∪ {y}) \ {b}, is also a γsp(G)-set. In such
a case, we define a new function f ′ : (C ∪ {b}) \ {y} −→ D′ where f ′(b) = f(y) and
f ′(w) = f(w) for everyw ∈ C\{y}. Since the subgraph induced by {x, f ′(x), b, f ′(b)} is
isomorphic to K2,2, we can conclude the proof using again Case 1. Analogously, suppose
that there exist x, y ∈ C such that f(y) /∈ N(f(x)) and N(x) ∩ C = {y}. If there exists
b ∈ B ∩N(x)∩N(f(y)), then we can take the γsp(G)-set D′ = (Dc ∪{f(x)}) \ {b} and
f ′ : (A ∪ {b}) \ {f(x)} −→ D′ where f ′(b) = x and f ′(f(z)) = z for every z ∈ C \ {x}
to obtain a subgraph isomorphic to K2,2. Applying again Case 1 we get the result.
End of Proof of Theorem 3.20.
The bound above is tight. For instance, for any graph H , adim(H ⊙ Nt) =
γsp(H ⊙ Nt) − 1 = |V (H)|t − 1 and for the Petersen graph shown in Figure 5 we have
adim(G) = γsp(G)− 1 = 3.
ORCID iDs
Sergio Bermudo https://orcid.org/0000-0003-4838-3170
José M. Rodrı́guez https://orcid.org/0000-0003-2851-7442
Juan A. Rodrı́guez-Velázquez https://orcid.org/0000-0002-9082-7647
José M. Sigarreta https://orcid.org/0000-0002-0863-4695
References
[1] A. F. Beardon and J. A. Rodrı́guez-Velázquez, On the k-metric dimension of metric spaces, Ars
Math. Contemp. 16 (2019), 25–38, doi:10.26493/1855-3974.1281.c7f.
[2] L. M. Blumenthal, Theory and Applications of Distance Geometry, Oxford, at the Clarendon
Press, 1953.
[3] R. C. Brigham, G. Chartrand, R. D. Dutton and P. Zhang, Resolving domination in graphs,
Math. Bohem. 128 (2003), 25–36.
[4] J. Cáceres, C. Hernando, M. Mora, I. M. Pelayo and M. L. Puertas, Locating-dominating codes:
bounds and extremal cardinalities, Appl. Math. Comput. 220 (2013), 38–45, doi:10.1016/j.amc.
2013.05.060.
[5] G. Chartrand, V. Saenpholphat and P. Zhang, The independent resolving number of a graph,
Math. Bohem. 128 (2003), 379–393.
[6] A. Estrada-Moreno, Y. Ramı́rez-Cruz and J. A. Rodrı́guez-Velázquez, On the adjacency dimen-
sion of graphs, Appl. Anal. Discrete Math. 10 (2016), 102–127, doi:10.2298/aadm151109022e.
[7] A. Estrada-Moreno, J. A. Rodrı́guez-Velázquez and I. G. Yero, The k-metric dimension of a
graph, Appl. Math. Inf. Sci. 9 (2015), 2829–2840, doi:10.12785/amis.
[8] A. Estrada-Moreno, I. G. Yero and J. A. Rodrı́guez-Velázquez, The k-metric dimension of
Corona product graphs, Bull. Malays. Math. Sci. Soc. 39 (2016), S135–S156, doi:10.1007/
s40840-015-0282-2.
402 Ars Math. Contemp. 22 (2022) #P3.02 / 387–402
[9] H. Fernau and J. A. Rodrı́guez-Velázquez, Notions of metric dimension of corona products:
combinatorial and computational results, in: Computer science—theory and applications,
Springer, Cham, volume 8476 of Lecture Notes in Comput. Sci., pp. 153–166, 2014, doi:
10.1007/978-3-319-06686-8\ 12.
[10] H. Fernau and J. A. Rodrı́guez-Velázquez, On the (adjacency) metric dimension of corona
and strong product graphs and their local variants: combinatorial and computational results,
Discrete Appl. Math. 236 (2018), 183–202, doi:10.1016/j.dam.2017.11.019.
[11] F. Harary and R. A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976), 191–
195.
[12] T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Domination in Graphs: Volume 2: Advanced
Topics, Taylor & Francis, 1998.
[13] T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of Domination in Graphs, vol-
ume 208 of Monographs and Textbooks in Pure and Applied Mathematics, Marcel Dekker, Inc.,
New York, 1998.
[14] C. Hernando, M. Mora and I. M. Pelayo, On global location-domination in graphs, Ars Math.
Contemp. 8 (2015), 365–379, doi:10.26493/1855-3974.591.5d0.
[15] M. Jannesari, Graphs with constant adjacency dimension, Discrete Math. Algorithms Appl.
(2021), doi:10.1142/s1793830921501342.
[16] M. Jannesari and B. Omoomi, The metric dimension of the lexicographic product of graphs,
Discrete Math. 312 (2012), 3349–3356, doi:10.1016/j.disc.2012.07.025.
[17] M. Lemańska, V. Swaminathan, Y. B. Venkatakrishnan and R. Zuazua, Super dominat-
ing sets in graphs, Proc. Nat. Acad. Sci. India Sect. A 85 (2015), 353–357, doi:10.1007/
s40010-015-0208-2.
[18] F. Okamoto, B. Phinezy and P. Zhang, The local metric dimension of a graph, Math. Bohem.
135 (2010), 239–255.
[19] B. S. Panda and A. Pandey, Algorithmic aspects of open neighborhood location-domination in
graphs, Discrete Appl. Math. 216 (2017), 290–306, doi:10.1016/j.dam.2015.03.002.
[20] Y. Ramı́rez-Cruz, A. Estrada-Moreno and J. A. Rodrı́guez-Velázquez, The simultaneous metric
dimension of families composed by lexicographic product graphs, Graphs Comb. 32 (2016),
2093–2120, doi:10.1007/s00373-016-1675-1.
[21] Y. Ramı́rez-Cruz, O. R. Oellermann and J. A. Rodrı́guez-Velázquez, The simultaneous metric
dimension of graph families, Discrete Appl. Math. 198 (2016), 241–250, doi:10.1016/j.dam.
2015.06.012.
[22] A. Sebő and E. Tannier, On metric generators of graphs, Math. Oper. Res. 29 (2004), 383–393,
doi:10.1287/moor.1030.0070.
[23] P. J. Slater, Leaves of trees, in: Proceedings of the Sixth Southeastern Conference on Com-
binatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1975),
Congressus Numerantium, No. XIV, 1975 pp. 549–559.
[24] P. J. Slater, Domination and location in acyclic graphs, Networks 17 (1987), 55–64, doi:10.
1002/net.3230170105.
[25] P. J. Slater, Dominating and reference sets in a graph, J. Math. Phys. Sci. 22 (1988), 445–455.
[26] H. Walikar, B. Acharya and E. Sampathkumar, Recent Developments in the Theory of Dom-
ination in Graphs and Its Applications, MRI Lecture Notes in mathematics, 1979, https:
//books.google.si/books?id=b4i-PgAACAAJ.