The Simultaneous Metric Dimension of Families Composed by Lexicographic Product Graphs

Abstract

Let $\mathcal{G}$ be a graph family defined on a common (labeled) vertex set V. A set $S\subseteq V$ is said to be a simultaneous metric generator for $\mathcal{G}$ if for every $G\in \mathcal{G}$ and every pair of different vertices $u,v\in V$ there exists $s\in S$ such that $d_{G}(s,u)\ne d_{G}(s,v)$, where $d_{G}$ denotes the geodesic distance. A simultaneous adjacency generator for $\mathcal{G}$ is a simultaneous metric generator under the metric $d_{G,2}(x,y)=\min \{d_{G}(x,y),2\}$. A minimum cardinality simultaneous metric (adjacency) generator for $\mathcal{G}$ is a simultaneous metric (adjacency) basis, and its cardinality the simultaneous metric (adjacency) dimension of $\mathcal{G}$. Based on the simultaneous adjacency dimension, we study the simultaneous metric dimension of families composed by lexicographic product graphs.

1 Introduction

A generator of a metric space (X, d) is a set $S\subset 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. Given a simple and connected graph $G=(V,E)$, we consider the function $d_G:V\times V\rightarrow \mathbb {N}\cup \{0\}$, where $d_G(x,y)$ is the length of a shortest path between u and v and $\mathbb {N}$ is the set of positive integers. Then $(V,d_G)$ is a metric space since $d_G$ satisfies (i) $d_G(x,x)=0$ for all $x\in V$, (ii) $d_G(x,y)=d_G(y,x)$ for all $x,y \in V$ and (iii) $d_G(x,y)\le d_G(x,z)+d_G(z,y)$ for all $x,y,z\in V$. A vertex $v\in V$ is said to distinguish two vertices x and y if $d_G(v,x)\ne d_G(v,y)$. A set $S\subset V$ is said to be a metric generator for G if any pair of vertices of G is distinguished by some element of S. A minimum cardinality metric generator is called a metric basis, and its cardinality the metric dimension of G, denoted by $\dim (G)$.

The notion of metric dimension of a graph was introduced by Slater in [20], where metric generators were called locating sets. Harary and Melter independently introduced the same concept in [10], where metric generators were called resolving sets. Applications of this invariant to the navigation of robots in networks are discussed in [15] and applications to chemistry in [13, 14]. Several variations of metric generators, including resolving dominating sets [1], independent resolving sets [3], local metric sets [16], strong resolving sets [19], adjacency resolving sets [12], k-metric generators [5, 6], simultaneous metric generators [17, 18], etc., have since been introduced and studied.

The concept of adjacency generator¹ was introduced by Jannesari and Omoomi in [12] 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 [7] 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 metric dimension of H. As a consequence of this strong relation they showed that the problem of computing the adjacency metric dimension is NP-hard. A set $S\subset V$ of vertices in a graph $G=(V,E)$ is said to be an adjacency generator for G if for every two vertices $x,y\in V-S$ there exists $s\in S$ such that s is adjacent to exactly one of x and y. A minimum cardinality adjacency generator is called an adjacency basis of G, and its cardinality the adjacency dimension of G, denoted by $\dim _A(G)$. Since any adjacency basis is a metric generator, $\dim (G)\le \dim _A(G)$. Besides, for any connected graph G of diameter at most two, $\dim _A(G)=\dim (G)$.

As pointed out in [7, 8], any adjacency generator of a graph $G=(V,E)$ is also a metric generator in a suitably chosen metric space. Given a positive integer t, we define the distance function $d_{G,t}:V\times V\rightarrow \mathbb {N}\cup \{0\}$, where

$$\begin{aligned} d_{G,t}(x,y)=\min \{d_G(x,y),t\}. \end{aligned}$$

(1)

Then any metric generator for $(V,d_{G,t})$ is a metric generator for $(V,d_{G,t+1})$ and, as a consequence, the metric dimension of $(V,d_{G,t+1})$ is less than or equal to the metric dimension of $(V,d_{G,t})$. In particular, the metric dimension of $(V,d_{G,1})$ is equal to $|V|-1$, the metric dimension of $(V,d_{G,2})$ is equal to $\dim _A(G)$ and, if G has diameter D(G), then $d_{G,D(G)}=d_G$ and so the metric dimension of $(V,d_{G,D(G)})$ is equal to $\dim (G)$. Notice that when using the metric $d_{G,t}$ the concept of metric generator needs not be restricted to the case of connected graphs.² Notice that S is an adjacency generator for G if and only if S is an adjacency generator for its complement $\overline{G}$. This is justified by the fact that given an adjacency generator S for G, it holds that for every $x,y\in V- S$ there exists $s\in S$ such that s is adjacent to exactly one of x and y, and this property holds in $\overline{G}$. Thus, $\dim _A(G)=\dim _A(\overline{G}).$

Let ${\mathcal G}=\{G_1,G_2,\ldots ,G_k\}$ be a family of (not necessarily edge-disjoint) connected graphs $G_i=(V,E_i)$ with common vertex set V (the union of whose edge sets is not necessarily the complete graph). Ramírez-Cruz, Oellermann and Rodríguez-Velázquez defined in [17, 18] a simultaneous metric generator for ${\mathcal {G}}$ as a set $S\subset V$ such that S is simultaneously a metric generator for each $G_i$. They say that a minimum simultaneous metric generator for ${\mathcal {G}}$ is a simultaneous metric basis of ${\mathcal {G}}$, and its cardinality the simultaneous metric dimension of ${\mathcal {G}}$, denoted by ${\text {Sd}}({\mathcal {G}})$ or explicitly by ${\text {Sd}}( G_1,G_2,\ldots ,G_k )$. Analogously, we define a simultaneous adjacency generator for $\mathcal{G}$ to be a set $S\subset V$ such that S is simultaneously an adjacency generator for each $G_i$. We say that a minimum simultaneous adjacency generator for $\mathcal{G}$ is a simultaneous adjacency basis of $\mathcal{G}$, and its cardinality the simultaneous adjacency dimension of $\mathcal{G}$, denoted by ${\text {Sd}}_A(\mathcal{G})$ or explicitly by ${\text {Sd}}_A(G_1,G_2,\ldots ,G_t)$. For instance, the set $\{v_1,v_3,v_5,v_8\}$ is a simultaneous adjacency basis of the family $\mathcal{G}=\{G_1,G_2,G_3\}$ shown in Fig. 1, while the set $\{v_1,v_5,v_8\}$ is a simultaneous metric basis, so ${\text {Sd}}_A(\mathcal{G})=4>3={\text {Sd}}(\mathcal{G})$.

Fig. 1

The set $\{v_1,v_3,v_5,v_8\}$ is a simultaneous adjacency basis of $\mathcal{G}=\{G_1,G_2,G_3\}$, whereas $\{v_1,v_5,v_8\}$ is a simultaneous metric basis

The study of simultaneous parameters in graphs was introduced by Brigham and Dutton in [2], where they studied simultaneous domination. This should not be confused with studies on families sharing a constant value on a parameter, for instance the study presented in [11], where several graph families such that all members have a constant metric dimension are studied, enforcing no constraints regarding whether all members share a metric basis or not. In particular, the study of the simultaneous metric dimension was introduced in [17, 18], where the authors obtained sharp bounds for this invariant for general families of graphs and gave closed formulae or tight bounds for the simultaneous metric dimension of several specific graph families. For a given graph G they described a process for obtaining a lower bound on the maximum number of graphs in a family containing G that has simultaneous metric dimension equal to $\dim (G)$. Moreover, it was shown that the problem of finding the simultaneous metric dimension of families of trees is NP-hard.

In this paper, we introduce the simultaneous adjacency dimension and study several of its properties, as well as its relations to the simultaneous metric dimension. We put a special focus on the usefulness of the simultaneous adjacency dimension as a tool for the study of the simultaneous metric dimension of families composed by lexicographic product graphs. Let G be a graph of order n, and let $(H_1,H_2,\ldots ,H_n)$ be an ordered n-tuple of graphs of order $n'_1,n'_2,\ldots ,n'_n$, respectively. The lexicographic product of G and $(H_1,H_2,\ldots ,H_n)$ is the graph $G \circ (H_1,H_2,\ldots ,H_n)$, such that $V(G \circ (H_1,H_2,\ldots ,H_n))=\bigcup _{u_i \in V(G)} (\{u_i\} \times V(H_i))$ and $(u_i,v_r)(u_j,v_s) \in E(G \circ (H_1,H_2,\ldots ,H_n))$ if and only if $u_iu_j \in E(G)$ or $i=j$ and $v_rv_s \in E(H_i)$. We will restrict our study to two particular cases. First, given two vertex-disjoint graphs $G=(V_{1},E_{1})$ and $H=(V_{2},E_{2})$, the join of G and H, denoted as $G+H$, is the graph with vertex set $V(G+H)=V_{1}\cup V_{2}$ and edge set $E(G+H)=E_{1}\cup E_{2}\cup \{uv\,:\,u\in V_{1},v\in V_{2}\}$. Join graphs are lexicographic product graphs, as $G+H \cong P_2 \circ (G,H)$. The other particular case we will focus on is the traditional lexicographic product graph, where $H_i \cong H$ for every $i \in \{1,\ldots ,n\}$, which is denoted as $G \circ H$ for simplicity.

The remainder of the paper is structured as follows. Section 2 covers general bounds and basic results on the simultaneous adjacency dimension. Section 3 is devoted to families composed by join graphs, whereas Sect. 4 covers families composed by standard lexicographic product graphs. Throughout the paper, we will use the notation $K_n$, $K_{r,s}$, $C_n$, $N_n$ and $P_n$ for complete graphs, complete bipartite graphs, cycle graphs, empty graphs and path graphs of order n, respectively. We use the notation $u \sim v$ if u and v are adjacent and $G \cong H$ if G and H are isomorphic graphs. For a vertex v of a graph G, $N_G(v)$ will denote the set of neighbours or open neighbourhood of v in G, i.e. $N_G(v)=\{u \in V(G):\; u \sim v\}$. The closed neighbourhood, denoted by $N_G[v]$, equals $N_G(v) \cup \{v\}$. If there is no ambiguity, we will simple write N(v) or N[v]. Two vertices $x,y\in V(G)$ are twins in G if $N_G[x]=N_G[y]$ or $N_G(x)=N_G(y)$. If $N_G[x]=N_G[y]$, they are said to be true twins, whereas if $N_G(x)=N_G(y)$ they are said to be false twins. We denote by $\delta (v)=|N(v)|$ the degree of vertex v, as well as $\delta (G)=\min _{v \in V(G)}\{\delta (v)\}$ and $\varDelta (G)=\max _{v \in V(G)}\{\delta (v)\}$. The subgraph of G induced by a set S of vertices is denoted by $\langle S\rangle _G$. If there is no ambiguity, we will simply write $\langle S\rangle$. The diameter of a graph G is denoted by D(G) and its girth by $\mathtt {g}(G)$. For the remainder of the paper, definitions will be introduced whenever a concept is needed.

2 Basic Results on the Simultaneous Adjacency Dimension

Remark 1

For any family $\mathcal{G}=\{G_1,G_2,\ldots ,G_k\}$ of connected graphs on a common vertex set V, the following results hold:

• (i) ${\text {Sd}}_A(\mathcal{G}) \ge \underset{i\in \{1,\ldots ,k\}}{\max }\{\dim _A(G_i)\}$.

• (ii) ${\text {Sd}}_A(\mathcal{G})\ge {\text {Sd}}(\mathcal{G})$.

• (iii) ${\text {Sd}}_A(\mathcal{G}) \le \vert V\vert -1$.

Proof

(i) is deduced directly from the definition of simultaneous adjacency dimension, while (iii) is obtained from the fact that for any non-trivial graph $G=(V,E)$ it holds that for any $v\in V$ the set $V-\{v\}$ is an adjacency generator. Let B be a simultaneous adjacency basis of $\mathcal{G}$ and let $u,v \in V-B$, be two different vertices. For every graph $G_i$, there exists $x \in B$ such that $d_{G_i,2}(u,x)\ne d_{G_i,2}(v,x)$, so $d_{G_i}(u,x) \ne d_{G_i}(v,x)$. Thus, B is a simultaneous metric generator for $\mathcal{G}$ and, as a consequence, (ii) follows.

As pointed out in [12], $\dim _A(G)=n-1$ if and only if $G=K_n$ or $G=N_n$. The following result follows directly from Remark 1.

Corollary 1

Let $\mathcal{G}$ be a graph family on a common vertex set V. If $K_{\vert V \vert } \in \mathcal{G}$ or $N_{\vert V \vert } \in \mathcal{G},$ then ${\text {Sd}}_A(\mathcal{G})=\vert V \vert - 1.$

The converse of Corollary 1 does not hold, as we will exemplify in Corollary 2. We first recall a characterization of the cases where ${\text {Sd}}(\mathcal{G})=|V|-1$, presented in [18].

Theorem 1

[18] Let ${\mathcal G}$ be a family of connected graphs on a common vertex set V. Then ${\text {Sd}}({\mathcal G})=\vert V\vert -1$ if and only if for every pair $u,v\in V,$ there exists a graph $G_{uv}\in {\mathcal G}$ such that u and v are twins in $G_{uv}.$

The following result is a direct consequence of Remark 1(ii), (iii) and Theorem 1.

Remark 2

Let ${\mathcal G}$ be a graph family on a common vertex set V. If for every pair $u,v\in V$, there exists a graph $G_{uv}\in {\mathcal G}$ such that u and v are twins in $G_{uv}$, then ${\text {Sd}}_A(\mathcal{G})=|V|-1$.

For a star graph $K_{1,r}$, $r \ge 3$, it is known that $\dim _A(K_{1,r})=r-1$ and every adjacency basis is composed by all but one of its leaves. For a finite set $V=\{v_1,v_2,\ldots ,v_n\}$, $n\ge 4$, let $K_{1,n-1}^i$ be the star graph having $v_i$ as its central vertex and $V-\{v_i\}$ as its leaves. We define the family $\mathcal{K}(V)=\{K_{1,n-1}^i :\; v_i \in V\}$. Any pair of vertices $v_p,v_q \in V$ are twins in every $K_{1,n-1}^i \in \mathcal{K}(V)-\{K_{1,n-1}^p,K_{1,n-1}^q\}$, so the following result is a direct consequence of Remark 2.

Corollary 2

For every finite set V of size $|V|\ge 4,$ ${\text {Sd}}_A(\mathcal{K}(V))=|V|-1.$

Let $P_3^{(1)}=(V,E_1)$, $P_3^{(2)}=(V,E_2)$ and $P_3^{(3)}=(V,E_3)$ be the three different path graphs defined on the common vertex set $V=\{v_1,v_2,v_3\}$, where $v_i$ is the vertex of degree two in $P_3^{(i)}$, for $i\in \{1,2,3\}$. It was shown in [12] that $\dim _A(G)=1$ if and only if $G \in \{P_1,P_2,P_3,\overline{P}_2,\overline{P}_3\}$. The following result follows directly from this fact.

Remark 3

The following statements hold:

• (i) ${\text {Sd}}_A(\mathcal{G})=1$ if and only if $\mathcal{G} \subseteq \{P_2,\overline{P}_2\}$, $\mathcal{G} \subseteq \{P_3^{(1)},P_3^{(2)},\overline{P}_3^{(1)},\overline{P}_3^{(2)}\}$, $\mathcal{G} \subseteq \{P_3^{(1)},P_3^{(3)},\overline{P}_3^{(1)},$ $\overline{P}_3^{(3)}\}$ or $\mathcal{G} \subseteq \{P_3^{(2)},P_3^{(3)},\overline{P}_3^{(2)},\overline{P}_3^{(3)}\}$.

• (ii) ${\text {Sd}}_A(P_3^{(1)}, P_3^{(2)},P_3^{(3)},\overline{P}_3^{(1)},\overline{P}_3^{(2)},\overline{P}_3^{(3)})=2$.

The following result is derived from the fact that any graph and its complement have the same adjacency bases.

Remark 4

Let $\mathcal{G}=\{G_1,G_2,\ldots ,G_k\}$ be a family of graphs with the same vertex set V, and let $\overline{\mathcal{G}}=\{\overline{G}_1,\overline{G}_2,\ldots ,\overline{G}_k\}$ be the family composed by the complements of every graph in $\mathcal{G}$. The following assertions hold:

• (i) ${\text {Sd}}_A(\mathcal{G})={\text {Sd}}_A(\overline{\mathcal{G}})={\text {Sd}}_A(\mathcal{G}\cup \overline{\mathcal{G}})$. Moreover, the simultaneous adjacency bases of $\mathcal{G}$ and $\overline{\mathcal{G}}$ coincide.

• (ii) For any subfamily of graphs $\mathcal{G}' \subseteq \overline{\mathcal{G}}$, ${\text {Sd}}_A(\mathcal{G})={\text {Sd}}_A(\mathcal{G} \cup \mathcal{G}')$.

Let $G=(V,E)$ be a graph and let ${\text {Perm}}(V)$ be the set of all permutations of V. Given a subset $X\subseteq V$, the stabilizer of X is the set of permutations

$$\begin{aligned} \mathcal{S}(X)=\{f\in {\text {Perm}}(V): f(x)=x, \; \text{ for } \text{ every } x\in X\}. \end{aligned}$$

As usual, we denote by f(X) the image of a subset X under f, i.e., $f(X)=\{f(x):\; x\in X\}$.

Let $G=(V,E)$ be a graph and let $B\subset V$ be a nonempty set. For any permutation $f\in \mathcal{S}(B)$ of V we say that a graph $G'=(V,E')$ belongs to the family $\mathcal{G}_{B,f}(G)$ if and only if $N_{G'}(x)=f(N_G(x))$, for every $x\in B$. We define the subgraph $\langle B_G\rangle _{w}=(N_G[B],E_{w})$ of G, weakly induced by B, where $N_G[B]=\cup _{x\in B}N_G[x]$ and $E_{w}$ is the set of all edges having at least one vertex in B. See Fig. 2 for an example of this construction.

Fig. 2

The graph $G=C_8$, and the subgraph $\langle B_G \rangle _w$ of G, weakly induced by the adjacency basis $B=\{v_1,v_3,v_7\}$. See that $N_G[B]=\{v_1,v_2,v_3,v_4,v_6,v_7,v_8\}$

Remark 5

Let $G=(V,E)$ be a graph and let $B\subset V$ be a nonempty set. For any $f\in \mathcal{{S}}(B)$ and any graph $G'\in \mathcal{{G}}_{B,f}(G)$,

$$\begin{aligned} \langle B_G \rangle _w \cong \langle B_{G'} \rangle _w. \end{aligned}$$

Proof

Since $G'\in \mathcal{G}_{B,f}(G)$, the function f is a bijection from V(G) onto $V(G')$. Now, since $N_{G'}(x)=f(N_G(x))$, for every $x\in B$, we conclude that uv is an edge of $\langle B_G \rangle _w$ if and only if f(u)f(v) is an edge of $\langle B_{G'} \rangle _w$. Therefore, the restriction of f to $\langle B_G \rangle _w$ is an isomorphism.

Now we define the family of graphs $\mathcal{G}_B(G)$, associated to B, as follows.

$$\begin{aligned} \mathcal{G}_B(G)=\bigcup _{f\in \mathcal{S}(B)}\mathcal{G}_{B,f}(G). \end{aligned}$$

With the above notation in mind, we can state our next result.

Theorem 2

Any adjacency basis B of a graph G is a simultaneous adjacency generator for any family of graphs $\mathcal{H} \subseteq \mathcal{G}_B(G).$ Moreover,  if $G\in \mathcal{H},$ then

$$\begin{aligned} {\text {Sd}}_A(\mathcal{H})=\dim _A(G). \end{aligned}$$

Proof

Assume that B is an adjacency basis of a graph $G=(V,E)$. Let $f\in \mathcal{S}(B)$ and let $G'=(V,E')$ such that $N_{G'}(x)=f(N_G(x))$, for every $x\in B$. We will show that B is an adjacency generator for any graph $G'$. To this end, we take two different vertices $u',v'\in V-B$ of $G'$ and the corresponding vertices $u,v\in V$ of G such that $f(u)=u'$ and $f(v)=v'$. Since $u\ne v$ and $u,v\not \in B$, there exists $x\in B$ such that $d_{G ,2}(u,x)\ne d_{G ,2}(v,x)$. Now, since $N_{G'}(x)=f(N_G(x))=\{f(w):\; w\in N_G(x)\}$, we obtain that $d_{G',2}(u',x)=d_{G,2}(u,x)\ne d_{G,2}(u,x) = d_{G',2}(v',x)$. Hence, B is an adjacency generator for $G'$ and, in consequence, is also a simultaneous adjacency generator for $\mathcal{H}$. Then we conclude that ${\text {Sd}}_A(\mathcal{H})\le |B| =\dim _A(G)$ and, if $G\in \mathcal{H}$, then ${\text {Sd}}_A(\mathcal{H})\ge \dim _A(G)$. Therefore, the result follows.

Fig. 3

A subfamily $\mathcal{H}$ of $\mathcal{G}_B(C_8)$ for $B=\{v_1,v_3,v_7\}$, where $\{H_1,H_2,H_3,H_4\} \subseteq \mathcal{G}_{B,f_1}(C_8)$ and $\{H_5,H_6,H_7,H_8\} \subseteq \mathcal{G}_{B,f_2}(C_8)$. For every $H_i \in \mathcal{H}$, $\dim _A(H_i)=\dim _A(C_8)=3$. Moreover, B is a simultaneous adjacency basis of $\mathcal{H}$, so ${\text {Sd}}_A(\mathcal{H})=3$

Notice that if $G\not \in \{K_n,N_n\}$, then the edge set of any graph $G'\in \mathcal{{G}}_B(G)$ can be partitioned into two sets $E_1$, $E_2$, where $E_1$ consists of all edges of G having at least one vertex in B and $E_2$ is a subset of edges of a complete graph whose vertex set is $V-B$. Hence, $\mathcal{{G}}_B(G)$ contains $2^{\frac{|V-B|(|V-B|-1)}{2}}|V-B|!$ different labelled graphs. As an example of large graph families that may be obtained according to this procedure, consider the cycle graph $C_8$, where $\dim _A(C_8)=3$. For each adjacency basis B of $C_8$, we have that $\vert \mathcal{G}_B(C_8) \vert = 122880$. To illustrate this, Fig. 3 shows a graph family $\mathcal{H}=\{H_1,\ldots ,H_8\} \subseteq \mathcal{G}_B(C_8)$, where $B=\{v_1,v_3,v_7\}$, $\{H_1,H_2,H_3,H_4\} \subseteq \mathcal{G}_{B,f_1}(C_8)$ and $\{H_5,H_6,H_7,H_8\} \subseteq \mathcal{G}_{B,f_2}(C_8)$.

The following result follows directly from Theorem 2 and the fact that $\dim _A(G)=1$ if and only if $G \in \{P_2,P_3,\overline{P}_2,\overline{P}_3\}$.

Corollary 3

Let G be a graph of order $n\ge 4.$ If $\dim _A(G)=2,$ then for any adjacency basis B of G and any non-empty subfamily $\mathcal{H} \subseteq \mathcal{G}_B(G),$

$$\begin{aligned} {\text {Sd}}_A(\mathcal{H})=2. \end{aligned}$$

The next result, obtained in [4], shows that Corollary 3 is only applicable to families of graphs of order 4, 5 or 6.

Remark 6

[4] If G is a graph of order $n\ge 7$, then $\dim _A(G)\ge 3$.

Theorem 2 and Remark 6 immediately lead to the next result.

Theorem 3

Let B be an adjacency basis of a graph G of order $n\ge 7.$ If $\dim _A(G)=3,$ then for any family $\mathcal{H}\subseteq \mathcal{G}_B(G),$

$$\begin{aligned} {\text {Sd}}_A(\mathcal{H})=3. \end{aligned}$$

The family $\mathcal{H}$ shown in Fig. 3 is an example of the previous result.

3 Families of Join Graphs

For a graph family $\mathcal{H}=\{H_1,H_2,\ldots ,H_{k}\}$, defined on common vertex set V, and the graph $K_1=\langle v \rangle$, $v \notin V$, we define the family

$$\begin{aligned} K_1+\mathcal{H}=\{K_1+H_i:\;1 \le i \le k\}. \end{aligned}$$

Notice that since for any $H_i \in \mathcal{H}$ the graph $K_1+H_i$ has diameter two,

$$\begin{aligned} {\text {Sd}}(K_1+\mathcal{H})={\text {Sd}}_A(K_1+\mathcal{H}). \end{aligned}$$

Theorem 4

Let $\mathcal{G}$ be a family of non-trivial graphs on a common vertex set V. If for every simultaneous adjacency basis B of $\mathcal{G}$ there exist $G \in \mathcal{G}$ and $x\in V$ such that $B\subseteq N_{G}(x),$ then

$$\begin{aligned} {\text {Sd}}(K_1+\mathcal{G})={\text {Sd}}_A(\mathcal{G})+1. \end{aligned}$$

Otherwise, 

$$\begin{aligned} {\text {Sd}}(K_1+\mathcal{G})={\text {Sd}}_A(\mathcal{G}). \end{aligned}$$

Proof

Let $V(K_1)=\{v_0\}$. Suppose that for every simultaneous adjacency basis B of $\mathcal{G}$ there exist $G \in \mathcal{G}$ and $x\in V$ such that $B\subseteq N_{G}(x)$. In this case, first notice that for every pair of different vertices $u,v \in V$ we have that $d_{K_1+G,2}(u,v_0)=d_{K_1+G,2}(v,v_0)=1$, so $v_0$ does not distinguish any pair of vertices. In consequence, a simultaneous metric basis of $K_1+\mathcal{G}$ must contain at least as many vertices as a simultaneous adjacency basis of $\mathcal{G}$. Secondly, since $B \subseteq N_{K_1+G}(v_0)$ and $B\subseteq N_{K_1+G}(x)$, a simultaneous metric basis of $K_1+\mathcal{G}$ must additionally contain some vertex $v \in (V-N_{G}(x))\cup \{v_0\}$, so ${\text {Sd}}(K_1+\mathcal{G}) \ge {\text {Sd}}_A(\mathcal{G})+1$. Let B be a simultaneous adjacency basis of $\mathcal{G}$ and let $B'=B\cup \{v_0\}$ and $G'\in \mathcal{G}$. For every pair of different vertices $u,v \in V(K_1+G')-B'$, there exists a vertex $z \in B\subset B'$ such that $d_{K_1+G',2}(u,z)=d_{G',2}(u,z) \ne d_{G',2}(v,z)=d_{K_1+G',2}(v,z)$, so $B'$ is a simultaneous metric generator for $K_1+\mathcal{G}$ and, as a result, ${\text {Sd}}(K_1+\mathcal{G}) \le |B'| = |B|+1= {\text {Sd}}_A(\mathcal{G})+1$. Consequently, ${\text {Sd}}(K_1+\mathcal{G})={\text {Sd}}_A(\mathcal{G})+1$.

Now suppose that there exists a simultaneous adjacency basis B of $\mathcal{G}$ such that $B \nsubseteq N_{G}(x)$ for every $G \in \mathcal{G}$ and every $x\in V$. In this case, first recall that a simultaneous metric basis of $K_1+\mathcal{G}$ must contain as many vertices as a simultaneous adjacency basis of $\mathcal{G}$, so ${\text {Sd}}(K_1+\mathcal{G}) \ge {\text {Sd}}_A(\mathcal{G})$. As above, for every pair of different vertices $u,v\in V-B$, there exists a vertex $z \in B$ such that $d_{K_1+G,2}(u,z)=d_{G,2}(u,z) \ne d_{G,2}(v,z)=d_{K_1+G,2}(v,z)$. Now, for any $u\in V-B$ there exists $u'\in B-N_{G}(u)$ such that $d_{K_1+G,2}(u,u')=2 \ne 1 =d_{K_1+G,2}(v_0,u')$. Hence, B is also a simultaneous metric generator for $K_1+\mathcal{G}$ and, consequently ${\text {Sd}}(K_1+\mathcal{G})\le |B|={\text {Sd}}_A(\mathcal{G})$. Therefore, ${\text {Sd}}(K_1+\mathcal{G})={\text {Sd}}_A(\mathcal{G})$.

Since $K_t+G=K_1+(K_{t-1}+G)$ for any $t \ge 2$, the previous result can be generalized as follows.

Corollary 4

Let $\mathcal{G}$ be a family of non-trivial graphs on a common vertex set V and let $K_t$ be a complete graph of order $t\ge 1.$ If for every simultaneous adjacency basis B of $\mathcal{G}$ there exist $G \in \mathcal{G}$ and $x\in V$ such that $B\subseteq N_{G}(x),$ then

$$\begin{aligned} {\text {Sd}}(K_t+\mathcal{G})={\text {Sd}}_A(\mathcal{G})+t. \end{aligned}$$

Otherwise, 

$$\begin{aligned} {\text {Sd}}(K_t+\mathcal{G})={\text {Sd}}_A(\mathcal{G})+t-1. \end{aligned}$$

By Remark 5 and Theorems 2 and 4 we deduce the following result.

Theorem 5

Let B be an adjacency basis of a graph G and let $\mathcal{H}\subseteq \mathcal{G}_B(G)$ such that $G\in \mathcal{H}.$ The following assertions hold : 

• (i) If for any adjacency basis $B'$ of G,  there exists $v\in V(G)$ such that $B' \subseteq N_G(v),$ then

  $$\begin{aligned} {\text {Sd}}(K_1+\mathcal{H})= \dim _A(G)+1. \end{aligned}$$

• (ii) If $B\not \subseteq N_G(v)$ for all $v\in V(G),$ then

  $$\begin{aligned} {\text {Sd}}(K_1+\mathcal{H})= \dim _A(G). \end{aligned}$$

Proof

First of all, by Theorem 2, ${\text {Sd}}_A(\mathcal{H})=\dim _A(G)$ and, as a consequence, every simultaneous adjacency basis of $\mathcal{H}$, which is also a simultaneous metric basis, is an adjacency basis of G. Now, if for any adjacency basis $B'$ of G, there exists $v\in V(G)$ such that $B' \subseteq N_G(v)$, then by Theorem 4, ${\text {Sd}}(K_1+\mathcal{H})={\text {Sd}}_A(\mathcal{H})+1=\dim _A(G)+1.$ Therefore, (i) follows. On the other hand, if $B\not \subseteq N_G(v)$ for all $v\in V(G)$, then by Remark 5 we have that for any $G'\in \mathcal{G}_B(G)$, $B\not \subseteq N_{G'}(v)$ for all $v\in V(G)$. Hence, by Theorem 4, ${\text {Sd}}(K_1+\mathcal{H})={\text {Sd}}_A(\mathcal{H})=\dim _A(G)$. Therefore, the proof of (ii) is complete.

To show some particular cases of the results above, we will state the following two results.

Remark 7

[12] For any integer $n\ge 4$,

$$\begin{aligned} \dim _A(P_n)=\dim _A(C_n)=\left\lfloor \frac{2n+2}{5}\right\rfloor . \end{aligned}$$

Lemma 1

Let G be a connected graph. If $D(G)\ge 6,$ or $G=C_n$ with $n\ge 7,$ or G is a graph of girth $\mathtt {g}(G)\ge 5$ and minimum degree $\delta (G)\ge 3,$ then for every adjacency generator B for G and every $v\in V(G),$ $B\not \subseteq N_G(v).$

Proof

Let B be an adjacency generator for G. First, suppose that there exists $v\in V(G)$ such that $B\subseteq N_G(v)$. Since B is an adjacency generator for G, either B is a dominating set or there exists exactly one vertex $u\in V(G)-B$ which is not dominated by B. In the first case, $D(G)\le 4$ and in the second one, either $D(G)\le 5$ or u is an isolated vertex. Hence, if $D(G)\ge 6$, then $B\not \subseteq N_G(v)$.

Now, assume that $\delta (G)\ge 3$. Let $v\in V(G)$, $u\in N_G(v)$ and $x,y\in N_G(u)-\{v\}$. If $\mathtt {g}(G)\ge 5$, then no vertex $z\in N_G[v]$ distinguishes x from y and, since B is an adjacency generator for G, there exists $z'\in B-N_G[v]$ which distinguishes them. Thus, $B\not \subseteq N_G(v)$.

Finally, if $G=C_n$ with $n\ge 7$, then by Remark 7 we have $|B|\ge \dim _A(G)=\left\lfloor \frac{2n+2}{5}\right\rfloor \ge 3$ and, since G has maximum degree two, the result follows.

According to Lemma 1, Theorem 4 immediately leads to the following result.

Proposition 1

Let $\mathcal{G}$ be a family of graphs on a common vertex set V of cardinality $|V|\ge 7$. If every $G\in \mathcal{G}$ satisfies $D(G)\ge 6,$ or $\mathtt {g}(G)\ge 5$ and $\delta (G)\ge 3,$ or it is a cycle graph,  then

$$\begin{aligned} {\text {Sd}}(K_1+\mathcal{G})={\text {Sd}}_A(\mathcal{G}). \end{aligned}$$

Theorem 5 and Lemma 1 immediately lead to the following result.

Proposition 2

Let G be a graph of order n and let B be an adjacency basis of G. If G is a cycle graph with $n\ge 7,$ or $D(G)\ge 6,$ or $\mathtt {g}(G) \ge 5$ and $\delta (G) \ge 3,$ then for any family $\mathcal{H} \subseteq \mathcal{G}_B(G)$ such that $G\in \mathcal{H},$

$$\begin{aligned} {\text {Sd}}(K_1+\mathcal{H})=\dim _A(G). \end{aligned}$$

We now discuss particular cases where ${\text {Sd}}(K_1+\mathcal{G})={\text {Sd}}_A(\mathcal{G})+1$. First, consider a graph family $\mathcal{G}=\{G_1,G_2,\ldots ,G_k\}$, defined on a common vertex set of cardinality n, such that $G_i \cong K_n$ for some $i \in \{1,\ldots ,k\}$. Since $K_1+K_n=K_{n+1}$, we have that ${\text {Sd}}(K_1+\mathcal{G})=n={\text {Sd}}_A(\mathcal{G})+1$. Now recall the families $\mathcal{K}(V)$ of star graphs defined in Sect. 2. The following result holds.

Proposition 3

For every finite set V of size $|V|\ge 4,$ ${\text {Sd}}(K_1 + \mathcal{K}(V))={\text {Sd}}_A(\mathcal{K}(V))+1.$

Proof

Every simultaneous adjacency basis B of $\mathcal{K}(V)$ has the form $V-\{v_i\}$, $i \in \{1,\ldots ,n\}$. In $K_{1,n-1}^i$, we have that $B \subseteq N_{K_{1,n-1}^i}(v_i)$, so the result is deduced by Theorem 4.

For two graph families $\mathcal{G}=\{G_1,G_2,\ldots ,G_{k_1}\}$ and $\mathcal{H}=\{H_1,H_2,\ldots ,H_{k_2}\}$, defined on common vertex sets $V_1$ and $V_2$, respectively, such that $V_1 \cap V_2 = \emptyset$, we define the family

$$\begin{aligned} \mathcal{G}+\mathcal{H}=\{G_i+H_j:\;1 \le i \le k_1, 1 \le j \le k_2\} . \end{aligned}$$

Notice that, since for any $G_i \in \mathcal{G}$ and $H_j \in \mathcal{H}$ the graph $G_i+H_j$ has diameter two,

$$\begin{aligned} {\text {Sd}}(\mathcal{G}+\mathcal{H})={\text {Sd}}_A(\mathcal{G}+\mathcal{H}). \end{aligned}$$

Theorem 6

Let $\mathcal{G}$ and $\mathcal{H}$ be two families of non-trivial graphs on common vertex sets $V_1$ and $V_2,$ respectively. If there exists a simultaneous adjacency basis B of $\mathcal{G}$ such that for every $G \in \mathcal{G}$ and every $g\in V_1,$ $B\not \subseteq N_G(g),$ then

$$\begin{aligned} {\text {Sd}}(\mathcal{G}+\mathcal{H})={\text {Sd}}_A(\mathcal{G})+{\text {Sd}}_A(\mathcal{H}). \end{aligned}$$

Proof

Let B be a simultaneous adjacency basis of $\mathcal{G}$ such that $B\nsubseteq N_G(u)$ for every $u\in V_1$, and let $B'$ be a simultaneous adjacency basis of $\mathcal{H}$. We claim that the set $S=B \cup B'$ is a simultaneous metric generator for $\mathcal{G+H}$. Consider a pair of different vertices $u,v\in (V_1 \cup V_2)-S$. If $u,v \in V_1$, then there exists $x \in B$ that distinguishes them in every $G \in \mathcal{G}$. An analogous situation occurs for $u,v \in V_2$. If $u \in V_1$ and $v \in V_2$, since $B\not \subseteq N_G(u)$, there exists $x \in B$ such that $d_{G+H,2}(u,x)=2 \ne 1=d_{G+H,2}(v,x)$ for every $G\in \mathcal{G}$ and $H\in \mathcal{H}$. Thus, S is a simultaneous metric generator for $\mathcal{G}+\mathcal{H}$ and, as a consequence, ${\text {Sd}}(\mathcal{G}+\mathcal{H}) \le \vert S \vert = \vert B \vert + \vert B' \vert = {\text {Sd}}_A(\mathcal{G})+{\text {Sd}}_A(\mathcal{H})$.

To prove that ${\text {Sd}}(\mathcal{G}+\mathcal{H}) \ge {\text {Sd}}_A(\mathcal{G})+{\text {Sd}}_A(\mathcal{H})$, consider a simultaneous metric basis W of $\mathcal{G}+\mathcal{H}$. Let $W_1=W \cap V_1$ and let $W_2=W\cap V_2$. Let $G\in \mathcal{G}$ and $H\in \mathcal{H}$. No pair of different vertices $u,v \in V_2-W_2$ is distinguished in $G+H$ by any vertex from $W_1$, whereas no pair of different vertices $u,v \in V_1-W_1$ is distinguished in $G+H$ by any vertex from $W_2$, so $W_1$ is a simultaneous adjacency generator for $\mathcal{G}$ and $W_2$ is a simultaneous adjacency generator for $\mathcal{H}$. Thus, ${\text {Sd}}(\mathcal{G}+\mathcal{H})=|W|= \vert W_1 \vert + \vert W_2 \vert \ge {\text {Sd}}_A(\mathcal{G})+{\text {Sd}}_A(\mathcal{H})$.

By Lemma 1 we deduce the following consequence of Theorem 6.

Corollary 5

Let $\mathcal{G}$ be a family of graphs on a common vertex set V of cardinality $|V|\ge 7.$ If every $G\in \mathcal{G}$ satisfies $D(G)\ge 6,$ or $\mathtt {g}(G) \ge 5$ and $\delta (G) \ge 3,$ or it is a cycle graph,  then for any family $\mathcal{H}$ of non-trivial graphs on a common vertex set, 

$$\begin{aligned} {\text {Sd}}(\mathcal{G + H})={\text {Sd}}_A(\mathcal{G})+{\text {Sd}}_A(\mathcal{H}). \end{aligned}$$

Theorems 2 and 6 and Lemma 1 immediately lead to the next result.

Theorem 7

Let G be a graph of order n and let B be an adjacency basis of G. If G is a cycle graph with $n\ge 7,$ or $D(G)\ge 6,$ or $\mathtt {g}(G)\ge 5$ and $\delta (G)\ge 3,$ then for any family $\mathcal{G}' \subseteq \mathcal{G}_B(G)$ such that $G\in \mathcal{G}'$ and any family $\mathcal{H}$ of non-trivial graphs on a common vertex set, 

$$\begin{aligned} {\text {Sd}}(\mathcal{G}'+\mathcal{H})=\dim _A(G)+{\text {Sd}}_A(\mathcal{H}). \end{aligned}$$

The ideas introduced in Theorem 2 allow us to define large families composed by subgraphs of a join graph $G+H$, which may be seen as the result of a relaxation of the join operation, in the sense that not every pair of nodes $u \in V(G)$, $v \in V(H)$, must be linked by an edge, yet any adjacency basis of $G+H$ is a simultaneous adjacency generator for the family, and thus a simultaneous metric generator. Since for any adjacency basis B of $G+H$, the family $\mathcal{R}_B$ defined in the next result is a subfamily of $\mathcal{G}_B(G+H)$, the result follows directly from Theorem 2.

Corollary 6

Let G and H be two non-trivial graphs and let B be an adjacency basis of $G+H$. Let $E'=\{uv \in E(G+H) :\; u \in V(G)-B,\; v \in V(H)-B\}$ and let $\mathcal{R}_B=\{R_1,R_2,\ldots ,R_k\}$ be a graph family,  defined on the common vertex set $V(G+H),$ such that,  for every $i \in \{1,\ldots ,k\},$ $E(R_i)=E(G+H)-E_i,$ for some edge subset $E_i \subseteq E'.$ Then

$$\begin{aligned} {\text {Sd}}(\mathcal{R}_B) \le \dim (G+H). \end{aligned}$$

As the next result shows, it is possible to obtain families composed by join graphs of the form $G'+H'$, where $G'$ and $H'$ are the result of applying modifications to G and H, respectively, in such a way that any adjacency basis of $G+H$ is a simultaneous adjacency generator for the family, and thus a simultaneous metric generator.

Corollary 7

Let G and H be two non-trivial graphs and let B be an adjacency basis of $G+H$. Let $B_1=B\cap V(G)$ and $B_2=B\cap V(H)$. Then for any family $\mathcal{H}\subseteq \mathcal{G}_{B_1}(G)+\mathcal{G}_{B_2}(H),$

$$\begin{aligned} {\text {Sd}}(\mathcal{H}) \le \dim (G+H). \end{aligned}$$

Moreover,  if $G+H\in \mathcal{H},$ then

$$\begin{aligned} {\text {Sd}}(\mathcal{H}) = \dim (G+H). \end{aligned}$$

Proof

The result is a direct consequence of Theorem 2, as $\mathcal{G}_{B_1}(G)+\mathcal{G}_{B_2}(H)\subseteq \mathcal{G}_B(G+H)$.

Given two families $\mathcal{G}$ and $\mathcal{H}$ of non-trivial graphs on common vertex sets $V_1$ and $V_2$, respectively, we define $\mathcal{B}(\mathcal{G})$ and $\mathcal{B}(\mathcal{H})$ as the sets composed by all simultaneous adjacency bases of $\mathcal{G}$ and $\mathcal{H}$, respectively. For a simultaneous adjacency basis $B \in \mathcal{B}(\mathcal{G})$, consider the set

$$\begin{aligned} P(B)=\{u \in V_1 :\; B\subseteq N_{G}(u)\text { for some } G\in \mathcal{G}\}. \end{aligned}$$

Similarly, for a simultaneous adjacency basis $B' \in \mathcal{B}(\mathcal{H})$, consider the set

$$\begin{aligned} Q(B')=\{v \in V_2 :\; B'\subseteq N_{H}(v)\text { for some } H\in \mathcal{H}\}. \end{aligned}$$

Based on the definitions of P(B) and $Q(B')$, we define the parameter $\psi ({ \mathcal G},\mathcal{H})$ as

$$\begin{aligned} \psi ({ \mathcal G},\mathcal{H})=\underset{B' \in \mathcal{B}(\mathcal{H})}{\underset{B \in \mathcal{B}(\mathcal{G}),}{\min }}\left\{ \vert P(B) \vert , \vert Q(B') \vert \right\} . \end{aligned}$$

The following result holds.

Theorem 8

Let $\mathcal{G}$ and $\mathcal{H}$ be two families of non-trivial graphs on common vertex sets $V_1$ and $V_2,$ respectively. If for every simultaneous adjacency basis $B_1$ of $\mathcal{G}$ there exists $G \in \mathcal{G}$ and $g\in V_1$ such that $B_1\subseteq N_G(g)$ and for every simultaneous adjacency basis $B_2$ of $\mathcal{H}$ there exists $H \in \mathcal{H}$ and $h\in V_2$ such that $B_2\subseteq N_H(h),$ then

$$\begin{aligned} {\text {Sd}}_A(\mathcal{G})+{\text {Sd}}_A(\mathcal{H})+1 \le {\text {Sd}}(\mathcal{G}+\mathcal{H}) \le {\text {Sd}}_A(\mathcal{G})+{\text {Sd}}_A(\mathcal{H})+\psi (\mathcal{G},\mathcal{H}). \end{aligned}$$

Proof

We first address the proof of the lower bound. Let W be a simultaneous metric basis of $\mathcal{G}+\mathcal{H}$ and let $W_1=W \cap V_1$ and $W_2=W \cap V_2$. Let $G\in \mathcal{G}$ and $H\in \mathcal{H}$. Since no pair of different vertices $u,v \in V_2-W_2$ is distinguished by any vertex in $W_1$, whereas no pair of different vertices $u,v \in V_1-W_1$ is distinguished by any vertex in $W_2$, we conclude that $W_1$ is an adjacency generator for G and $W_2$ is an adjacency generator for H. Hence, $W_1$ is a simultaneous adjacency generator for $\mathcal{G}$ and $W_2$ is a simultaneous adjacency generator for $\mathcal{H}$. If $W_1$ is a simultaneous adjacency basis of $\mathcal{G}$ and $W_2$ is a simultaneous adjacency basis of $\mathcal{H}$, then under the assumptions of this theorem, for at least one graph $G+H\in \mathcal{G+H}$ there exist $x \in V_1-W_1$ and $y \in V_2-W_2$, such that $W\subseteq N_{G+H}(x)$ and $W\subseteq N_{G+H}(y)$, which is a contradiction. Thus, $W_1$ is not a simultaneous adjacency basis of $\mathcal{G}$ or $W_2$ is not a simultaneous adjacency basis of $\mathcal{H}$. Hence, $\vert W_1 \vert \ge {\text {Sd}}_A(\mathcal{G})+1$ or $\vert W_2 \vert \ge {\text {Sd}}_A(\mathcal{H})+1$. In consequence, we have that ${\text {Sd}}(\mathcal{G}+\mathcal{H})=|W|= \vert W_1 \vert + \vert W_2 \vert \ge {\text {Sd}}_A(\mathcal{G})+{\text {Sd}}_A(\mathcal{H})+1$.

We now address the proof of the upper bound. Let $B_1$ and $B_2$ be simultaneous adjacency bases of $\mathcal{G}$ and $\mathcal{H}$, respectively, for which $\psi ({ \mathcal G},\mathcal{H})$ is obtained. Assume, without loss of generality, that $\vert P(B_1) \vert \le \vert Q(B_2) \vert$. Let $S=B_1 \cup B_2 \cup P(B_1)$. We claim that S is a simultaneous metric generator for $\mathcal{G}+\mathcal{H}$. To show this, we differentiate two cases for any $G \in \mathcal{G}$ and $H \in \mathcal{H}$.

Case 1 There exists $g\in V_1$ such that $B_1\subseteq N_G(g)$. We claim that the set $S'=B_1 \cup B_2 \cup \{g\}\subseteq S$ is a metric generator for $G+H$. To see this, we only need to check that for any $u\in V_1-(B_1\cup \{g\})$ and $v\in V_2-B_2$ there exists $s\in S'$ which distinguishes them, as $B_1$ and $B_2$ are adjacency generators for G and H, respectively. That is, since g is the sole vertex in $V_1$ satisfying $N_G(g)\supseteq B_1$, for any $u\in V_1-(B_1\cup \{g\})$ and $v\in V_2-B_2$ there exists $s\in B_1\subset S'$ such that $d_{G+H,2}(u,s)=2 \ne 1= d_{G+H,2}(v,s)$. Hence, the set $S'\subseteq S$ is a metric generator for $G+H$.

Case 2 No vertex $g\in V_1$ satisfies $B_1\subseteq N_G(g)$. In this case, the set $S'=B_1 \cup B_2 \subseteq S$ is a metric generator for $G+H$, as $B_1$ and $B_2$ are adjacency generators for G and H, respectively, and for any $u\in V_1-B_1$ and $v\in V_2-B_2$ there exists $s\in B_1\subset S'$ such that $d_{G+H,2}(u,s)=2 \ne 1= d_{G+H,2}(v,s)$.

Therefore, S is a simultaneous metric generator for $\mathcal{G}+\mathcal{H}$, so ${\text {Sd}}(\mathcal{G}+\mathcal{H}) \le \vert S \vert = \vert B_1 \vert + \vert B_2 \vert + \vert P(B_1) \vert = {\text {Sd}}_A(\mathcal{G})+{\text {Sd}}_A(\mathcal{H})+\psi ({ \mathcal G},\mathcal{H})$.

As the following corollary shows, the inequalities above are tight.

Corollary 8

Let $\mathcal{G}=\{G_1, G_2, \ldots , G_k\}$ and $\mathcal{G}'=\{G'_1, G'_2, \ldots , G'_{k'}\}$ be families composed by paths and/or cycle graphs on common vertex sets V and $V'$ of sizes $n \ge 7$ and $n' \ge 7,$ respectively. Let $u,v \notin V\cup V',$ $u\ne v,$ and let $\mathcal{H}=\{\langle u \rangle + G_1, \langle u \rangle + G_2, \ldots , \langle u \rangle + G_k\}$ and $\mathcal{H}'=\{\langle v \rangle + G'_1, \langle v \rangle + G'_2, \ldots , \langle v \rangle + G'_{k'}\}.$ Then, 

$$\begin{aligned} {\text {Sd}}(\mathcal{H}+\mathcal{H}')={\text {Sd}}_A(\mathcal{H})+{\text {Sd}}_A(\mathcal{H}')+1. \end{aligned}$$

Proof

By Lemma 1 we have that for every simultaneous adjacency generator B for $G\in \mathcal{G}$ and every $v\in V(G)$, $B\not \subseteq N_G(v).$ Hence, as we have shown in the proof of Theorem 4, any simultaneous adjacency basis of $\mathcal{G}$ is a simultaneous adjacency basis of $K_1+\mathcal{G}\cong \langle u\rangle +\mathcal{G}=\mathcal{H}$ and vice versa. So, for any simultaneous adjacency basis B of $\mathcal{H}$ we have that $P(B)=\{u\}$. Analogously, for any simultaneous adjacency basis $B'$ of $\mathcal{H}'$, we have $Q(B')=\{v\}$ and so $\psi ({ \mathcal H},\mathcal{H'})=1$.

Notice that the result above can be extended to any pair of graph families $\mathcal{G}$ and $\mathcal{G}'$ satisfying the premises of Lemma 1.

4 Families of Standard Lexicographic Product Graphs

Note that the lexicographic product of two graphs is not a commutative operation. Moreover, $G\circ H$ is a connected graph if and only if G is connected. We would point out the following known result.

Claim

[9] Let G and H be two non-trivial graphs such that G is connected. Then the following assertions hold for any $a,c\in V(G)$ and $b,d\in V(H)$ such that $a\ne c.$

• (i) $N_{G\circ H}(a,b)=\left( \{a\}\times N_H(b)\right) \cup \left( N_G(a)\times V(H)\right)$.

• (ii) $d_{G\circ H}((a,b),(c,d)) = d_{G}(a,c)$

• (iii) $d_{G\circ H}((a,b),(a,d)) = d_{H,2}(b,d)$.

Several results on the metric dimension of the lexicographic product $G \circ H$ of two graphs G and H, and its relation to the adjacency dimension of H, are presented in [12]. In this section, we study the simultaneous metric dimension of several families composed by lexicographic product graphs, exploiting the simultaneous adjacency dimension as an important tool.

First, we introduce some necessary notation. Let S be a subset of $V(G \circ H)$. The projection of S onto V(G) is the set $\{u:\;(u ,v) \in S\}$, whereas the projection of S onto V(H) is the set $\{v :\;(u,v) \in S\}$. We define the twin equivalence relation $\mathcal{T}$ on V(G) as follows:

$$\begin{aligned} x \mathcal{T} y \Longleftrightarrow N_G[x]=N_G[y]\quad \hbox {or}\quad N_G(x)=N_G(y). \end{aligned}$$

In what follows, we will denote the equivalence class of vertex x by $x^*=\{y\in V(G):\; y\mathcal{T} x\}$. Notice that every equivalence class may be a singleton set, a clique of size at least two of G or an independent set of size at least two of G. We will refer to equivalence classes which are non-singleton cliques as true twin equivalence classes and to equivalence classes which are non-singleton independent sets as false twin equivalence classes. From now on, T(G) denotes the set of all true twin equivalence classes in V(G), whereas F(G) denotes the set of all false twin equivalence classes in V(G). Finally, $V_T(G)$ and $V_F(G)$ denote the sets of vertices belonging to true and false twin equivalence classes, respectively.

For two graph families $\mathcal{G}=\{G_1,G_2,\ldots ,G_{k_1}\}$ and $\mathcal{H}=\{H_1,H_2,\ldots ,H_{k_2}\}$, defined on common vertex sets $V_1$ and $V_2$, respectively, we define the family

$$\begin{aligned} \mathcal{G}\circ \mathcal{H}=\{G_i \circ H_j:\;1 \le i \le k_1, 1 \le j \le k_2\}. \end{aligned}$$

In particular, if $\mathcal{G}=\{G\}$ we will use the notation $G \circ \mathcal{H}$.

Our first result allows to extend any result on the simultaneous adjacency dimension of $\mathcal{G}\circ \mathcal{H}$ to the simultaneous metric dimension, and vice versa.

Theorem 9

Let G be a connected graph and let H be a non-trivial graph. Then,  every metric generator for $G \circ H$ is also an adjacency generator,  and vice versa.

Proof

By definition, every adjacency generator for $G \circ H$ is also a metric generator, so we only need to prove that any metric generator for $G \circ H$ is also an adjacency generator. Let S be a metric generator for $G \circ H$. For a vertex $u_i \in V(G)$, let $R_i=\{u_i\} \times V(H)$. Notice that $R_i \cap S\ne \emptyset$, for every $u_i \in V(G)$, as no vertex outside of $\{u_i\}\times V(H)$ distinguishes pairs of vertices in $\{u_i\}\times V(H)$. We differentiate the following cases for two different vertices $(u_i,v_r),(u_j,v_s)\in V(G \circ H)-S$:

• 1. $i = j$. In this case, no vertex from $R_x \cap S$, $x \ne i$, distinguishes $(u_i,v_r)$ and $(u_j,v_s)$, so there exists $(u_i,v) \in R_i \cap S$ such that $d_{G \circ H,2}((u_i,v_r),(u_i,v))=d_{G \circ H}((u_i,v_r),(u_i,v)) \ne d_{G \circ H}((u_j,v_s),(u_i,v))=d_{G \circ H,2}((u_j,v_s),(u_i,v))$.

• 2. $u_i$ and $u_j$ are true twins $(i \ne j)$. Here, no vertex from $R_x \cap S$, $x \notin \{i,j\}$, distinguishes $(u_i,v_r)$ and $(u_j,v_s)$, so there exists $(u_i,v)\in R_i \cap S$ such that $d_{G \circ H,2}((u_i,v_r),(u_i,v))=d_{G \circ H}((u_i,v_r),(u_i,v))=2 \ne 1=d_{G \circ H}((u_j,v_s),(u_i,v))=d_{G \circ H,2}((u_j,v_s),(u_i,v))$, or there exists $(u_j,v)\in R_j \cap S$ such that $d_{G \circ H,2}((u_i,v_r),(u_j,v))=d_{G \circ H}((u_i,v_r),(u_j,v))=1 \ne 2=d_{G \circ H}((u_j,v_s),(u_j,v))=d_{G \circ H,2}((u_j,v_s),(u_j,v))$.

• 3. $u_i$ and $u_j$ are false twins ($i \ne j$). As in the previous case, no vertex from $R_x \cap S$, $x \notin \{i,j\}$, distinguishes $(u_i,v_r)$ and $(u_j,v_s)$, so there exists $(u_i,v)\in R_i \cap S$ such that $d_{G \circ H,2}((u_i,v_r),(u_i,v))=d_{G \circ H}((u_i,v_r),(u_i,v))=1 \ne 2=d_{G \circ H}((u_j,v_s),(u_i,v))=d_{G \circ H,2}((u_j,v_s),(u_i,v))$, or there exists $(u_j,v)\in R_j \cap S$ such that $d_{G \circ H,2}((u_i,v_r),(u_j,v))=d_{G \circ H}((u_i,v_r),(u_j,v))=2 \ne 1=d_{G \circ H}((u_j,v_s),(u_j,v))=d_{G \circ H,2}((u_j,v_s),(u_j,v))$.

• 4. $u_i$ and $u_j$ are not twins. In this case, there exists $u_x \in V(G)-\{u_i,u_j\}$ such that $d_{G,2}(u_i,u_x)\ne d_{G,2}(u_j,u_x)$. Hence, for any $(u_x,v) \in R_x \cap S$ we have that $d_{G \circ H,2}((u_i,v_r),(u_x,v))=d_{G,2}(u_i,u_x)$ $\ne d_{G,2}(u_j,u_x)=d_{G \circ H,2}((u_j,v_s),$ $(u_x,v))$.

In conclusion, S is an adjacency generator for $G \circ H$. The proof is complete.

Corollary 9

For any connected graph and any non-trivial graph H, 

$$\begin{aligned} \dim (G \circ H)=\dim _A(G \circ H). \end{aligned}$$

In general,  for every family $\mathcal{G}$ composed by connected graphs on a common vertex set,  and every family $\mathcal{H}$ composed by non-trivial graphs on a common vertex set, 

$$\begin{aligned} {\text {Sd}}(\mathcal{G}\circ \mathcal{H})={\text {Sd}}_A(\mathcal{G}\circ \mathcal{H}). \end{aligned}$$

We would point out that the equalities above hold, even for lexicographic product graphs of diameter greater than two.

The following result, presented in [12], gives a lower bound on $\dim (G \circ H)$, which depends on the order of G and $\dim _A(H)$.

Theorem 10

[12] Let G be a connected graph of order n and let H be a non-trivial graph. Then $\dim (G \circ H) \ge n\cdot \dim _A(H).$

We now generalise the previous result for families composed by lexicographic product graphs.

Theorem 11

Let $\mathcal{G}$ be a family of connected graphs on a common vertex set $V_1$ and let $\mathcal{H}$ be a family of non-trivial graphs on a common vertex set $V_2$. Then

$$\begin{aligned} {\text {Sd}}(\mathcal{G}\circ \mathcal{H}) \ge \vert V_1 \vert \cdot {\text {Sd}}_A(\mathcal{H}). \end{aligned}$$

Proof

It was shown in [12] that if $S'$ is a metric generator for $G \circ H$, and $R_i = \{u_i\} \times V(H)$ for some $u_i \in V(G)$, then $S' \cap R_i$ resolves all vertex pairs in $R_i$, and the projection of $S' \cap R_i$ onto V(H) is an adjacency generator for H. Following an analogous reasoning, consider a simultaneous metric generator S for $\mathcal{G}\circ \mathcal{H}$, and let $R_i=\{u_i\} \times V_2$ for some $u_i \in V_1$. We have that the projection of $S \cap R_i$ onto $V_2$ is an adjacency generator for every $H \in \mathcal{H}$ and, in consequence, a simultaneous adjacency generator for $\mathcal{H}$, so $|R_i \cap S|\ge {\text {Sd}}_A(\mathcal{H})$. Thus, ${\text {Sd}}(\mathcal{G}\circ \mathcal{H})=|S|={\sum _{u_i \in V_1}|R_i \cap S|} \ge |V_1|\cdot {\text {Sd}}_A(\mathcal{H})$.

In order to present our next results, we introduce some additional definitions. For a graph family $\mathcal{G}$, defined on a common vertex set V, let $V_M(\mathcal{G})=\{u :\; u \in V_T(G), u \in V_F(G') \text { for some } G,G' \in \mathcal{G}\}$. Moreover, for a family $\mathcal{H}$ composed by $k_2$ non-trivial graphs on a common vertex set $V'$, let $\mathcal{B}_1(\mathcal{H})$ be the set of simultaneous adjacency bases B of $\mathcal{H}$ satisfying $B \nsubseteq N_{H}(v)$ for every $H \in \mathcal{H}$ and every $v \in V'$, and let $\mathcal{B}_2(\mathcal{H})$ be the set of simultaneous adjacency bases of $\mathcal{H}$ that are also dominating sets of every $H \in \mathcal{H}$. Finally, we define the parameter

$$\begin{aligned} \zeta (\mathcal{H})=\min \left\{ k_2,\underset{\underset{B_2 \in \mathcal{B}_2(\mathcal{H})}{_{B_1 \in \mathcal{B}_1(\mathcal{H})}}}{\min } \left\{ \vert B_2 - B_1 \vert \right\} \right\} . \end{aligned}$$

With these definitions in mind, we give the next result.

Theorem 12

Let $\mathcal{G}=\{G_1,G_2,\ldots ,G_{k_1}\}$ be a family of connected graphs on a common vertex set $V_1,$ let $\mathcal{H}=\{H_1,H_2,\ldots ,H_{k_2}\}$ be a family of non-trivial graphs, defined on a common vertex set $V_2,$ such that $\mathcal{B}_1(\mathcal{H})$ and $\mathcal{B}_2(\mathcal{H})$ are not empty,  and let $\overline{\mathcal{H}}=\{\overline{H}_1,\overline{H}_2,\ldots ,\overline{H}_{k_2}\}$. If $V_M(\mathcal{G})=\emptyset$ or $\mathcal{B}_1(\mathcal{H}) \cap \mathcal{B}_2(\mathcal{H}) \ne \emptyset ,$ then

$$\begin{aligned} {\text {Sd}}(\mathcal{G} \circ \mathcal{H})={\text {Sd}}(\mathcal{G} \circ \overline{\mathcal{H}})=\vert V_1 \vert \cdot {\text {Sd}}_A(\mathcal{H}). \end{aligned}$$

(2)

Otherwise, 

$$\begin{aligned} |V_1| \cdot {\text {Sd}}_A(\mathcal{H})+|V_M(\mathcal{G})|\le & {} {\text {Sd}}(\mathcal{G} \circ \mathcal{H})\nonumber \\= & {} {\text {Sd}}(\mathcal{G} \circ \overline{\mathcal{H}}) \le |V_1| \cdot {\text {Sd}}_A(\mathcal{H}) + \zeta (\mathcal{H}) \cdot |V_M(\mathcal{G})|. \end{aligned}$$

(3)

Proof

We first assume that $V_M(\mathcal{G})=\emptyset$. By Theorem 11, we have that ${\text {Sd}}(\mathcal{G} \circ \mathcal{H}) \ge |V_1|\cdot {\text {Sd}}_A(\mathcal{H})$. Thus, it only remains to prove that ${\text {Sd}}(\mathcal{G} \circ \mathcal{H}) \le |V_1|\cdot {\text {Sd}}_A(\mathcal{H})$. To this end, consider the partition $\{V'_1,V''_1\}$ of $V_1$, where $V'_1=\{u:\;u \in V_T(G)\text { for some }G \in \mathcal{G}\}$, and a pair of simultaneous adjacency bases $B_1 \in \mathcal{B}_1(\mathcal{H})$ and $B_2 \in \mathcal{B}_2(\mathcal{H})$. Consider the set

$$\begin{aligned} S=(V'_1 \times B_1) \cup (V''_1 \times B_2). \end{aligned}$$

It was shown in [12] that a set constructed in this manner, considering $\mathcal{G}=\{G\}$ and $\mathcal{H}=\{H\}$, is a metric generator for $G \circ H$. Following an analogous reasoning, we shall deduce that S is also a metric generator for every $G \circ H\in \mathcal{G}\circ \mathcal{H}$, and thus a simultaneous metric generator for $\mathcal{G} \circ \mathcal{H}$. For the sake of thoroughness of our discussion, we elaborate the four cases for two different vertices $(u_i,v_r),(u_j,v_s)\in V(G\circ H)-S$:

• 1. $i=j$. In this case, $r\ne s$. Let $R_i=\{u_i\} \times V_2$. Since $S\cap R_i=\{u_i\}\times B_1$ or $S\cap R_i=\{u_i\}\times B_2$ and both $B_1$ and $B_2$ are adjacency generators for H, there exists $v \in B_1$ such that $d_{H,2}(v,v_r)\ne d_{H,2}(v,v_s)$, or there exists $v \in B_2$ such that $d_{H,2}(v,v_r)\ne d_{H,2}(v,v_s)$. Since for every $(u_i,v_r),(u_i,v_s)\in R_i$ we have that $d_{G \circ H,2}((u_i,v_r),(u_i,v_s))=d_{H,2}(v_r,v_s)$, we conclude that at least one element from S distinguishes $(u_i,v_r)$ and $(u_i,v_s)$.

• 2. $i\ne j$ and $u_i,u_j$ are true twins. Here, since $B_1 \nsubseteq N_{H}(v_r)$, there exists $v\in B_1$ such that $d_{H,2}(v_r,v)=2$. Thus, $d_{G \circ H,2}((u_i,v_r),(u_i,v))=d_{H,2}(v_r,v)=2\ne 1=d_{G,2}(u_j,u_i)=d_{G \circ H,2}((u_j,v_s),(u_i,v))$.

• 3. $i\ne j$ and $u_i,u_j$ are false twins. Here, since $B_2$ is a dominating set of H, there exists $v\in B_2$ such that $d_{H,2}(v_r,v)=1$. Thus, $d_{G \circ H,2}((u_i,v_r),(u_i,v))$ $=d_{H,2}(v_r,v)=1\ne 2=d_{G,2}(u_j,u_i)=d_{G \circ H,2}((u_j,v_s),(u_i,v))$.

• 4. $i\ne j$ and $u_i,u_j$ are not twins. Here, there exists $u_z \in V_1$ such that $d_{G,2}(u_i,u_z)\ne d_{G,2}(u_j,u_z)$. Since $S \cap R_z\ne \emptyset$, we have that $d_{G \circ H,2}((u_i,v_r),$ $(u_z,v))=d_{G,2}(u_i,u_z)\ne d_{G,2}(u_j,u_z)=d_{G \circ H,2}((u_j,v_s),(u_z,v))$ for every $(u_z,v)\in S$.

Therefore, S is a metric generator for every $G \circ H \in \mathcal{G} \circ \mathcal{H}$ and, in consequence, a simultaneous metric generator for $\mathcal{G} \circ \mathcal{H}$. Hence, ${\text {Sd}}(\mathcal{G} \circ \mathcal{H}) \le \vert S \vert = |V_1|\cdot {\text {Sd}}_A(\mathcal{H})$ and the equality holds.

We now address the proof of ${\text {Sd}}(\mathcal{G} \circ \overline{\mathcal{H}})=|V_1| \cdot {\text {Sd}}_A(\mathcal{H})$. As pointed out in [12], $B_1$ is a dominating set of every $\overline{H} \in \overline{\mathcal{H}}$ and $B_2$ satisfies $B_2 \nsubseteq N_{\overline{H}}(v)$ for every $\overline{H} \in \overline{\mathcal{H}}$ and every $v \in V_2$. Since ${\text {Sd}}_A(\mathcal{H})={\text {Sd}}_A(\overline{\mathcal{H}})$, by exchanging the roles of $B_1$ and $B_2$ and proceeding in a manner analogous to the one used for proving that ${\text {Sd}}(\mathcal{G} \circ \mathcal{H})\le |V_1|\cdot {\text {Sd}}_A(\mathcal{H})$, we obtain that ${\text {Sd}}(\mathcal{G} \circ \overline{\mathcal{H}}) \le |V_1|\cdot {\text {Sd}}_A(\overline{\mathcal{H}})=|V_1|\cdot {\text {Sd}}_A(\mathcal{H})$. Since ${\text {Sd}}(\mathcal{G} \circ \overline{\mathcal{H}}) \ge |V_1|\cdot {\text {Sd}}_A(\overline{\mathcal{H}})=|V_1|\cdot {\text {Sd}}_A(\mathcal{H})$ by Theorem 11, the equality holds.

From now on, we assume that $V_M(\mathcal{G}) \ne \emptyset$ and $\mathcal{B}_1(\mathcal{H}) \cap \mathcal{B}_2(\mathcal{H}) \ne \emptyset$. Consider a simultaneous adjacency basis $B \in \mathcal{B}_1(\mathcal{H}) \cap \mathcal{B}_2(\mathcal{H})$. By a reasoning analogous to the one previously shown, we have that the set $S=V_1 \times B$ is a metric generator for every $G \circ H \in \mathcal{G}\circ \mathcal{H}$ and every $G \circ \overline{H} \in \mathcal{G}\circ \overline{\mathcal{H}}$. Consequently, S is a simultaneous metric generator for $\mathcal{G} \circ \mathcal{H}$ and $\mathcal{G} \circ \overline{\mathcal{H}}$, so ${\text {Sd}}(\mathcal{G} \circ \mathcal{H}) \le \vert S \vert = \vert V_1 \vert \cdot {\text {Sd}}_A(\mathcal{H})$ and ${\text {Sd}}(\mathcal{G} \circ \overline{\mathcal{H}}) \le \vert S \vert = \vert V_1 \vert \cdot {\text {Sd}}_A(\mathcal{H})$. By Theorem 11, ${\text {Sd}}(\mathcal{G} \circ \mathcal{H}) \ge \vert V_1 \vert \cdot {\text {Sd}}_A(\mathcal{H})$ and ${\text {Sd}}(\mathcal{G} \circ \overline{\mathcal{H}}) \ge \vert V_1 \vert \cdot {\text {Sd}}_A(\mathcal{H})$, so the equalities hold.

From now on, we assume that $V_M(\mathcal{G}) \ne \emptyset$ and $\mathcal{B}_1(\mathcal{H}) \cap \mathcal{B}_2(\mathcal{H}) = \emptyset$. Let B be a simultaneous metric basis of $\mathcal{G} \circ \mathcal{H}$ and let $B_p=B \cap (\{u_p\} \times V_2)$ for some $u_p \in V_1$. Recall that, as shown in the proof of Theorem 11, the projection of $B_p$ onto $V_2$ is a simultaneous adjacency generator for $\mathcal{H}$. Let $B'_p$ be the projection onto $V_2$ of some $B_p$ such that $u_p \in V_M(\mathcal{G})$. Suppose, for the purpose of contradiction, that $|B'_p|={\text {Sd}}_A(\mathcal{H})$. Let $G \in \mathcal{G}$ be a graph where $u_p \in V_T(G)$ and let $G' \in \mathcal{G}$ be a graph where $u_p \in V_F(G')$. We have that there exists $v \in V_2-B'_p$ such that either $B'_p \subseteq N_{H'}(v)$ for some $H' \in \mathcal{H}$ or $B'_p \cap N_{H''}(v)=\emptyset$ for some $H'' \in \mathcal{H}$. In the first case, no vertex $(x,y)\in B$ distinguishes in $G \circ H'$ the vertex $(u_p,v)$ from any vertex $(u_t,w)$ such that $u_p$ and $u_t$ are true twins in G, whereas in the second case, no vertex $(x,y) \in B$ distinguishes in $G' \circ H''$ the vertex $(u_p,v)$ from any vertex $(u_f,w)$ such that $u_p$ and $u_f$ are false twins in $G'$. In either case, we have a contradiction with the fact that B is a simultaneous metric basis of $\mathcal{G}\circ \mathcal{H}$. Thus, for every $u_p \in V_M(\mathcal{G})$, we have that $\vert B_p \vert = \vert B'_p \vert \ge {\text {Sd}}_A(\mathcal{H})+1$. In conclusion,

$$\begin{aligned} {\text {Sd}}(\mathcal{G} \circ \mathcal{H})= & {} \vert B \vert = {\sum _{u_p \in V_1-V_M(\mathcal{G})}}\vert B_p \vert + {\sum _{u_p \in V_M(\mathcal{G})}} \vert B_p \vert \\\ge & {} {\sum _{u_p \in V_1-V_M(\mathcal{G})}}{\text {Sd}}_A(\mathcal{H}) + {\sum _{u_p \in V_M(\mathcal{G})}}({\text {Sd}}_A(\mathcal{H})+1)\\= & {} \vert V_1-V_M(\mathcal{G}) \vert \cdot {\text {Sd}}_A(\mathcal{H})+\vert V_M(\mathcal{G}) \vert \cdot ({\text {Sd}}_A(\mathcal{H})+1)\\= & {} \vert V_1 \vert \cdot {\text {Sd}}_A(\mathcal{H})+\vert V_M(\mathcal{G}) \vert . \end{aligned}$$

In order to prove the upper bound, consider the partition $\{V_M(\mathcal{G}),V'_1,V''_1\}$ of $V_1$, where $V'_1=\{u:\;u \in V_T(G)\text { for some }G \in \mathcal{G}\}$. Since $\mathcal{B}_1(\mathcal{H})$ and $\mathcal{B}_2(\mathcal{H})$ are disjoint, for any $B_1 \in \mathcal{B}_1(\mathcal{H})$ and $B_2 \in \mathcal{B}_2(\mathcal{H})$, there exist up to $k_2$ vertices $v_{p_1},v_{p_2},\ldots ,v_{p_r} \in V_2-B_1$ such that $B_1 \cap N_{H}(v_{p_i})=\emptyset$ for some $H \in \mathcal{H}$ and up to $k_2$ vertices $v_{q_1},v_{q_2},\ldots ,v_{q_s} \in V_2-B_2$ such that $B_2 \subseteq N_{H}(v_{q_i})$ for some $H \in \mathcal{H}$. We define the sets $B'_1=B_1 \cup \{v_{p_1},v_{p_2},\ldots ,v_{p_r}\}$ and $B'_2=B_2 \cup \{v_{q_1},v_{q_2},\ldots ,v_{q_s}\}$, which are simultaneous adjacency generators for $\mathcal{H}$ that are also dominating sets of every $H \in \mathcal{H}$ and satisfy $B'_1 \nsubseteq N_{H}(w)$ and $B'_2 \nsubseteq N_{H}(w)$ for every $w \in V_2$ and every $H \in \mathcal{H}$.

Consider one $B_1 \in \mathcal{B}_1(\mathcal{H})$ such that $|B'_1|$ is minimum and any $B_2 \in \mathcal{B}_2(\mathcal{H})$. We define the set $S_1=(V'_1 \times B_1) \cup (V''_1 \times B_2) \cup (V_M(\mathcal{G}) \times B'_1)$. Likewise, consider one $B_2 \in \mathcal{B}_2(\mathcal{H})$ such that $|B'_2|$ is minimum and any $B_1 \in \mathcal{B}_1(\mathcal{H})$. We define the set $S_2=(V'_1 \times B_1) \cup (V''_1 \times B_2) \cup (V_M(\mathcal{G}) \times B'_2)$. Finally, consider a pair of simultaneous adjacency bases $B_1 \in \mathcal{B}_1(\mathcal{H})$ and $B_2 \in \mathcal{B}_2(\mathcal{H})$ such that $|B_1 \cup B_2|$ is minimum. As $\vert B_1 \vert = \vert B_2 \vert$, we have that $\vert B_2 - B_1 \vert = \vert B_1 - B_2 \vert$ and is also minimum. We define the set $S_3=(V'_1 \times B_1) \cup (V''_1 \times B_2) \cup (V_M(\mathcal{G}) \times (B_1 \cup B_2))$. Now, recall that for every $G \in \mathcal{G}$ the sets $S=(V_T(G) \times B_1) \cup ((V_1-V_T(G)) \times B_2)$ and $S'=((V_1-V_F(G)) \times B_1) \cup (V_F(G) \times B_2)$ are metric generators for every $G \circ H \in \mathcal{G}\circ \mathcal{H}$. Clearly, $S \subseteq S_1$ or $S' \subseteq S_1$, whereas $S \subseteq S_2$ or $S' \subseteq S_2$, and $S \subseteq S_3$ or $S' \subseteq S_3$, so we have that $S_1$, $S_2$ and $S_3$ are simultaneous metric generators for $\mathcal{G}\circ \mathcal{H}$. Thus,

$$\begin{aligned} {\text {Sd}}(\mathcal{G} \circ \mathcal{H})\le & {} \min \{\vert S_1 \vert , \vert S_2 \vert , \vert S_3 \vert \}\\= & {} \vert V_1-V_M(\mathcal{G}) \vert \cdot {\text {Sd}}_A(\mathcal{H})\\&+\, \vert V_M(\mathcal{G}) \vert \cdot \min \left\{ {\min _{B_1 \in \mathcal{B}_1(\mathcal{H})}}\{\vert B'_1 \vert \},{\min _{B_2 \in \mathcal{B}_2(\mathcal{H})}}\{\vert B'_2 \vert \},\underset{\underset{B_2 \in \mathcal{B}_2(\mathcal{H})}{_{B_1 \in \mathcal{B}_1(\mathcal{H})}}}{\min } \{\vert B_1 \cup B_2 \vert \}\right\} \\\le & {} \vert V_1-V_M(\mathcal{G}) \vert \cdot {\text {Sd}}_A(\mathcal{H}) + \vert V_M(\mathcal{G}) \vert \cdot \left( {\text {Sd}}_A(\mathcal{H})+\zeta (\mathcal{H})\right) \\= & {} \vert V_1 \vert \cdot {\text {Sd}}_A(\mathcal{H}) + \zeta (\mathcal{H}) \cdot \vert V_M(\mathcal{G}) \vert . \end{aligned}$$

As in the previous cases, by exchanging the roles of $\mathcal{B}_1$ and $\mathcal{B}_2$ for $\overline{\mathcal{H}}$ and proceeding in an analogous manner as above, we obtain that

$$\begin{aligned} \vert V_1 \vert \cdot {\text {Sd}}_A(\mathcal{H})+\vert V_M(\mathcal{G}) \vert \le {\text {Sd}}(\mathcal{G} \circ \overline{\mathcal{H}}) \le \vert V_1 \vert \cdot {\text {Sd}}_A(\mathcal{H}) + \zeta (\mathcal{H}) \cdot \vert V_M(\mathcal{G}) \vert . \end{aligned}$$

The proof is thus complete.

We now analyse the different cases described in Theorem 12. First, note that if $\zeta (\mathcal{H})=1$, then Eq. 3 becomes an equality. In particular, $\zeta (\mathcal{H})=1$ for every $\mathcal{H}=\{H\}$. Additionally, if there exists a simultaneous adjacency basis $B_1 \in \mathcal{B}_1(\mathcal{H})$ such that one vertex $v \in V_2-B_1$ satisfies $B_1 \cap N_{H}(v)=\emptyset$ for every $H \in \mathcal{H}$, then $\zeta (\mathcal{H})=1$. In an analogous manner, if there exists a simultaneous adjacency basis $B_2 \in \mathcal{B}_2(\mathcal{H})$ such that one vertex $v \in V_2-B_2$ satisfies $B_2 \subseteq N_{H}(v)$ for every $H \in \mathcal{H}$, then $\zeta (\mathcal{H})=1$. Finally, if there exist two simultaneous adjacency bases $B_1 \in \mathcal{B}_1(\mathcal{H})$ and $B_2 \in \mathcal{B}_2(\mathcal{H})$ such that $|B_1 \cup B_2| = {\text {Sd}}_A(\mathcal{H})+1$, then $\zeta (\mathcal{H})=1$.

Next, we discuss Eq. 2. First, note that $V_M(\{G\})=\emptyset$ for every graph G. Now, we analyse several non-trivial conditions under which a graph family $\mathcal{G}$ composed by connected graphs on a common vertex set satisfies $V_M(\mathcal{G})=\emptyset$. Consider two vertices u and v that are true twins in some graph G, and a vertex $x \in V(G)-\{u,v\}$ such that $x \sim u$ and $x \sim v$. We have that $\langle \{u,v,x\}\rangle _G \cong C_3$. This fact allows us to characterize a large number of families composed by true-twins-free graphs, for which $V_M(\mathcal{G})=\emptyset$.

Remark 8

Let $\mathcal{G}$ be a graph family on a common vertex set, such that every $G\in \mathcal{G}$ is a tree or satisfies $\mathtt {g}(G)\ge 4$. Then, $V_M(\mathcal{G})=\emptyset$.

In particular, for families composed by path or cycle graphs of order greater than or equal to four, not only all members are true-twins-free, but they are also false-twins-free. Moreover, families composed by hypercubes of degree $r \ge 2$ satisfy that all their members have girth four.

We now study the behaviour of $V_M(\mathcal{H})$ for $\mathcal{H} \subseteq \mathcal{G}_B(G)$, where B is an adjacency basis of G.

Remark 9

For every adjacency basis B of a graph G, and every family $\mathcal{H} \subseteq \mathcal{G}_B(G)$, $V_M(\mathcal{H})=\emptyset$.

Proof

Let B be an adjacency basis of G. Consider a pair of vertices $x,y \in B$. By the construction of $\mathcal{G}_B(G)$, we have that in every $H \in \mathcal{H}$ either x and y are true twins, or they are false twins, or they are not twins. Moreover, since B is a simultaneous adjacency generator for $\mathcal{H}$, no pair of vertices $x,y \in V(G)-B$ are twins in any $H \in \mathcal{H}$. Finally, consider two vertices $x \in B$ and $y \in V(G)-B$. If there exist graphs $H_1,H_2,\ldots ,H_k \in \mathcal{H}$ where $N_{H_i}(x)=N_{H_i}(y)$, $i \in \{1,\ldots ,k\}$, we have that, by the construction of $\mathcal{G}_B(G)$, either $x \sim y$ in every $H_i$, $i \in \{1,\ldots ,k\}$, or $x \not \sim y$ in every $H_i$, $i \in \{1,\ldots ,k\}$. Hence, x and y are true twins in every $H_i$, $i \in \{1,\ldots ,k\}$, or they are false twins in every $H_i$, $i \in \{1,\ldots ,k\}$. In consequence, $V_M(\mathcal{H})=\emptyset$.

We now discuss several cases where a graph family $\mathcal{H}$ satisfies $\mathcal{B}_1(\mathcal{H}) \cap \mathcal{B}_2(\mathcal{H}) \ne \emptyset$. First, we introduce an auxiliary result.

Lemma 2

Let $P_n$ and $C_n$ be a path and a cycle graph of order $n \ge 7.$ If $n \mod 5 \in \{0,2,4\},$ then there exist adjacency bases of $P_n$ and $C_n$ that are dominating sets.

Proof

In $C_n$, consider the path $v_iv_{i+1}v_{i+2}v_{i+3}v_{i+4}$, where the subscripts are taken modulo n, and an adjacency basis B. If $v_i,v_{i+2} \in B$ and $v_{i+1} \notin B$, then $\{v_{i+1}\}$ is said to be a 1-gap of B. Likewise, if $v_i,v_{i+3} \in B$ and $v_{i+1},v_{i+2} \notin B$, then $\{v_{i+1},v_{i+2}\}$ is said to be a 2-gap of B and if $v_i,v_{i+4} \in B$ and $v_{i+1},v_{i+2},v_{i+3} \notin B$, then $\{v_{i+1},v_{i+2},v_{i+3}\}$ is said to be a 3-gap of B. Since B is an adjacency basis of $C_n$, it has no gaps of size 4 or larger and it has at most one 3-gap. Moreover, every 2- or 3-gap must be neighboured by two 1-gaps and the number of gaps of either size is at most $\dim _A(C_n)$. We now differentiate the following cases for $C_n$:

• 1. $n=5k$, $k\ge 2$. In this case, $\dim _A(C_n)=2k$ and $n-\dim _A(C_n)=3k$. Since any 2-gap must be neighboured by two 1-gaps, any adjacency basis has at most k 2-gaps. Any set B having exactly k 2-gaps and exactly k 1-gaps is an adjacency basis of $C_n$, as $|B|\ge 2k=\dim _A(C_n)$ and $|(N_{C_n}(x) \cap B) \triangledown (N_{C_n}(y) \cap B)| \ge 1$ for any pair of different vertices $x,y \in V(C_n)-B$. Since the number of vertices of $V(C_n)-B$ belonging to a 1- or 2-gap is $3k=n-|B|$, we deduce that B has no 3-gaps, i.e. it is a dominating set.

• 2. $n=5k+2$, $k\ge 1$. In this case, $\dim _A(C_n)=2k+1$ and $n-\dim _A(C_n)=3k+1$. As in the previous case, any adjacency basis has at most k 2-gaps. Moreover, any set B having exactly k 2-gaps and exactly $k+1$ 1-gaps is an adjacency basis of $C_n$, and the number of vertices of $V(C_n)-B$ belonging to a 1- or 2-gap is $3k+1=n-|B|$, so B has no 3-gaps, i.e. it is a dominating set.

• 3. $n=5k+4$, $k\ge 1$. In this case, $\dim _A(C_n)=2k+2$ and $n-\dim _A(C_n)=3k+2$. Assume that some adjacency basis B has $k+1$ 2-gaps. Then, B would have at least $k+1$ 1-gaps, making $|V(C_n)-B|\ge 3k+3$, which is a contradiction. So, any adjacency basis has at most k 2-gaps. As in the previous cases, any set B having exactly k 2-gaps and exactly $k+2$ 1-gaps is an adjacency basis of $C_n$, and the number of vertices of $V(C_n)-B$ belonging to a 1- or 2-gap is $3k+2=n-|B|$, so B has no 3-gaps, i.e. it is a dominating set.

By the set of cases above, the result holds for $C_n$.

Now consider the path $P_n$, where $n \mod 5 \in \{0,2,4\}$, and let $C'_n$ be the cycle obtained from $P_n$ by joining its leaves $v_1$ and $v_n$ by an edge. Let B be an adjacency basis of $C'_n$ which is also a dominating set and satisfies $v_1,v_n \notin B$ (at least one such B exists). We have that every $u \in B$ and every $v \in V(P_n)-B$ satisfy $d_{C'_n,2}(u,v)=d_{P_n,2}(u,v)$, so B is also an adjacency basis and a dominating set of $P_n$.

The following results hold.

Remark 10

Let $P_n$ be a path graph of order $n \ge 7$, where $n \mod 5 \in \{0,2,4\}$, and let $C_n$ be the cycle graph obtained from $P_n$ by joining its leaves by an edge. Let B be an adjacency basis of $P_n$ and $C_n$ which is also a dominating set of both. Then, every $\mathcal{H} \subseteq \mathcal{G}_B(P_n)\cup \mathcal{G}_B(C_n)$ such that $P_n \in \mathcal{H}$ or $C_n \in \mathcal{H}$ satisfies $\mathcal{B}_1(\mathcal{H}) \cap \mathcal{B}_2(\mathcal{H}) \ne \emptyset$.

Proof

The existence of B is a consequence of Lemma 2. Since $P_n \in \mathcal{H}$ or $C_n \in \mathcal{H}$, we have that B is a simultaneous adjacency basis of $\mathcal{H}$. Let $V=V(P_n)=V(C_n)$. By the definition of $\mathcal{G}_B$, we have that ${\bigcup _{v \in B}}N_{H}(v)={\bigcup _{v \in B}}N_{P_n}(v)=V$ or ${\bigcup _{v \in B}}N_{H}(v)={\bigcup _{v \in B}}N_{C_n}(v)=V$ for every $H \in \mathcal{H}$, so B is a dominating set of every $H \in \mathcal{H}$. Moreover, by Lemma 1, we have that $B \nsubseteq N_{P_n}(v)$ and $B \nsubseteq N_{C_n}(v)$ for every $v \in V$. Furthermore, by the definition of $\mathcal{G}_B$, we have that $B \cap N_{H}(v)=B \cap N_{P_n}(v)$ or $B \cap N_{H}(v)=B \cap N_{C_n}(v)$ for every $H \in \mathcal{H}$ and every $v\in V$, so $B \nsubseteq N_{H}(v)$ for every $H \in \mathcal{H}$ and every $v\in V$. In consequence, $B \in \mathcal{B}_1(\mathcal{H}) \cap \mathcal{B}_2(\mathcal{H})$, so the result holds.

The following result is a direct consequence of Theorem 12 and Remark 10.

Proposition 4

Let $\mathcal{G}$ be a family of connected graphs on a common vertex set V,  let $P_n$ be a path graph of order $n \ge 7,$ where $n~\mod ~5 \in \{0,2,4\},$ and let $C_n$ be the cycle graph obtained from $P_n$ by joining its leaves by an edge. Let B be an adjacency basis of $P_n$ and $C_n$ which is also a dominating set of both. Then,  for every $\mathcal{H} \subseteq \mathcal{G}_B(P_n)\cup \mathcal{G}_B(C_n)$ such that $P_n \in \mathcal{H}$ or $C_n \in \mathcal{H},$

$$\begin{aligned} {\text {Sd}}(\mathcal{G} \circ \mathcal{H})=|V|\cdot \left\lfloor \frac{2n+2}{5}\right\rfloor . \end{aligned}$$

Remark 11

Let $\mathcal{H}$ be a graph family on a common vertex set V of cardinality $|V|\ge 7$ such that every $H\in \mathcal{H}$ satisfies $D(H)\ge 6$, or $\mathtt {g}(H) \ge 5$ and $\delta (H) \ge 3$, or it is a cycle graph. Let $\mathcal{H}'$ be a graph family on a common vertex set $V'$ of cardinality $|V'|\ge 7$ satisfying the same conditions as $\mathcal{H}$. Then, $\mathcal{B}_1(\mathcal{H}+\mathcal{H}') \cap \mathcal{B}_2(\mathcal{H}+\mathcal{H}') \ne \emptyset$.

Proof

As we discussed in the proof of Theorem 6, there exists a simultaneous metric basis B of $\mathcal{H}+\mathcal{H}'$, which is also a simultaneous adjacency basis, such that the sets $W=B\cap V$ and $W'=B\cap V'$ satisfy $W \nsubseteq N_{H}(v)$ for every $H \in \mathcal{H}$ and every $v \in V$, and $W' \nsubseteq N_{H'}(w)$ for every $H' \in \mathcal{H}'$ and every $w \in V'$. In consequence, we have that $B \nsubseteq N_{H+H'}(v)$ for every $H+H' \in \mathcal{H}+\mathcal{H}'$ and every $v \in V \cup V'$. Moreover, every vertex in V is dominated by every vertex in $W'$, whereas every vertex in $V'$ is dominated by every vertex in W, so B is a dominating set for every $H+H' \in \mathcal{H}+\mathcal{H}'$. In consequence, $B \in \mathcal{B}_1(\mathcal{H}+\mathcal{H}') \cap \mathcal{B}_2(\mathcal{H}+\mathcal{H}')$, so the result holds.

By an analogous reasoning, Theorems 2 and 6 lead to the next result.

Remark 12

Let H be a graph of order n which satisfies $D(H)\ge 6$, or $\mathtt {g}(H) \ge 5$ and $\delta (H) \ge 3$, or it is a cycle graph with $n \ge 7$. Let $H'$ be a graph satisfying the same conditions as H. Let B and $B'$ be adjacency bases of H and $H'$, respectively. Then, any pair of families $\mathcal{H} \subseteq \mathcal{G}_B(H)$ and $\mathcal{H}' \subseteq \mathcal{G}_{B'}(H')$ such that $H \in \mathcal{H}$ and $H' \in \mathcal{H}'$ satisfies $\mathcal{B}_1(\mathcal{H}+\mathcal{H}') \cap \mathcal{B}_2(\mathcal{H}+\mathcal{H}') \ne \emptyset$.

The two following results are direct consequences of Theorem 12 and Remarks 11 and 12.

Proposition 5

Let $\mathcal{G}$ be a family of connected graphs on a common vertex set $V_1.$ Let $\mathcal{H}$ be a graph family on a common vertex set $V_2$ of cardinality $|V_2|\ge 7$ such that every $H\in \mathcal{H}$ satisfies $D(H)\ge 6,$ or $\mathtt {g}(H) \ge 5$ and $\delta (H) \ge 3,$ or it is a cycle graph. Let $\mathcal{H}'$ be a graph family on a common vertex set $V'_2$ of cardinality $|V'_2|\ge 7$ satisfying the same conditions as $\mathcal{H}$. Then, 

$$\begin{aligned} {\text {Sd}}(\mathcal{G} \circ (\mathcal{H}+\mathcal{H}'))=|V_1| \cdot {\text {Sd}}_A(\mathcal{H})+|V_1| \cdot {\text {Sd}}_A(\mathcal{H}'). \end{aligned}$$

Proposition 6

Let $\mathcal{G}$ be a family of connected graphs on a common vertex set V. Let H be a graph of order n which satisfies $D(H)\ge 6,$ or $\mathtt {g}(H) \ge 5$ and $\delta (H) \ge 3,$ or it is a cycle graph with $n \ge 7.$ Let $H'$ be a graph satisfying the same conditions as H. Let B and $B'$ be adjacency bases of H and $H',$ respectively. Then,  for any pair of families $\mathcal{H} \subseteq \mathcal{G}_B(H)$ and $\mathcal{H}' \subseteq \mathcal{G}_{B'}(H')$ such that $H \in \mathcal{H}$ and $H' \in \mathcal{H}',$

$$\begin{aligned} {\text {Sd}}(\mathcal{G} \circ (\mathcal{H}+\mathcal{H}'))=|V| \cdot \dim _A(H)+|V| \cdot \dim _A(H'). \end{aligned}$$

We now analyse several conditions under which a graph family $\mathcal{G}$ composed by connected graphs on a common vertex set satisfies $V_M(\mathcal{G}) \ne \emptyset$ and, in some cases, we exactly determine the value of $V_M(\mathcal{G})$. It is simple to see that any graph of the form $K_t+G$, $t \ge 2$, satisfies $V(K_t) \subseteq v^*$ for some $v^* \in T(K_t+G)$. Likewise, any graph of the form $N_t+G$, $t \ge 2$, satisfies $V(N_t) \subseteq v^*$ for some $v^* \in F(N_t+G)$. Moreover, any complete graph $K_n$, $n \ge 2$, satisfies $T(G)=\{V(K_n)\}$. The next results are direct consequences of these facts.

Remark 13

Let $\mathcal{G}=\{G_1,G_2,\ldots ,G_k\}$ be a family of connected graphs on a common vertex set V such that, for some $i \in \{1,\ldots ,k\}$, $G_i=N_t+G'$, where $N_t$ is an empty graph on the vertex set $V' \subset V$, $|V'| \ge 2$, and $G'=(V-V',E')$. If, for some $j \in \{1,\ldots ,k\}-\{i\}$, $G_j=K_t+G''$, where $K_t$ is a complete graph on the vertex set $V'$ and $G''=(V-V',E'')$, then $V_M(\mathcal{G}) \ne \emptyset$.

Corollary 10

Let $\mathcal{G}=\{G_1,G_2,\ldots ,G_k\}$ be a family composed by path or cycle graphs on a common vertex set $V_1$ of size $n \ge 4,$ and let $\{K_t,N_t\}$ be a family composed by a complete and an empty graph on a common vertex set $V_2$ of size $t \ge 2.$ Then every $\mathcal{H} \subseteq \{N_t+G_1,N_t+G_2,\ldots ,N_t+G_k\},$ $\mathcal{H}\ne \emptyset ,$ and every $\mathcal{H}' \subseteq \{K_{n+t}, K_t+G_1,K_t+G_2,\ldots ,K_t+G_k\},$ $\mathcal{H}'\ne \emptyset ,$ satisfy $V_M(\mathcal{H} \cup \mathcal{H}')=V_2.$

We now analyse cases of families containing a graph and its complement.

Remark 14

Let G be a connected graph such that $|T(G)|\ge 1$ or $|F(G)|\ge 1$, and $\overline{G}$ is connected. Then any family $\mathcal{G}$ composed by connected graphs on a common vertex set such that $G \in \mathcal{G}$ and $\overline{G} \in \mathcal{G}$ satisfies $V_M(\mathcal{G})\ne \emptyset$.

Proof

First assume that $|T(G)|\ge 1$. Consider a true twin equivalence class $v_1^*=\{v_1,v_2,\ldots ,v_t\} \in T(G)$. For every pair of vertices $v_i,v_j\in v_1^*$, we have that $N_{\overline{G}}(v_i)=N_{\overline{G}}(v_j)$ and $v_i \not \sim _{\overline{G}} v_j$. In consequence, $v_1^*$ is a false twin equivalence class of $\overline{G}$. Now assume that $|F(G)|\ge 1$ and consider a false twin equivalence class $w_1^*=\{w_1,w_2,\ldots ,w_f\} \in F(G)$. For every pair of vertices $w_i,w_j\in w_1^*$, we have that $N_{\overline{G}}[w_i]=N_{\overline{G}}[w_j]$, so $w_1^*$ is a true twin equivalence class of $\overline{G}$. In consequence, $V_T(G) \cup V_F(G) \subseteq V_M(\mathcal{G})$, so the result follows.

Corollary 11

For every connected graph G such that $\overline{G}$ is connected, 

$$\begin{aligned} V_M(\{G,\overline{G}\})=V_T(G) \cup V_F(G). \end{aligned}$$

Finally, we analyse some examples of families $\mathcal{H}$ satisfying $\mathcal{B}_1(\mathcal{H}) \cap \mathcal{B}_2(\mathcal{H}) = \emptyset$. Consider the family $\mathcal{H}_5=\{P_5,C_5\}$, where $V(P_5)=V(C_5)=\{v_1,v_2,v_3,v_4,$ $v_5\}$, $E(P_5)=\{v_1v_2,v_2v_3,v_3v_4,$ $v_4v_5\}$ and $E(C_5)=E(P_5) \cup \{v_1v_5\}$. We have that $\mathcal{B}_1(\mathcal{H}_5)=\{\{v_1,v_5\},\{v_2,v_3\},$ $\{v_3,v_4\}\}$ and $\mathcal{B}_2(\mathcal{H}_5)=\{\{v_2,v_4\}\}$, that is $\mathcal{B}_1(\mathcal{H}_5) \cap \mathcal{B}_2(\mathcal{H}_5) = \emptyset$. Likewise, $\mathcal{B}_1(\{P_5\})=\{\{v_1,v_5\},\{v_2,v_3\},\{v_3,v_4\}\}$ and $\mathcal{B}_2(\{P_5\})=\{\{v_2,v_4\}\}$, i.e. $\mathcal{B}_1(\{P_5\}) \cap \mathcal{B}_2(\{P_5\}) = \emptyset$; whereas $\mathcal{B}_1(\{C_5\})=\{\{v_1,v_2\},\{v_1,v_5\},\{v_2,v_3\},$ $\{v_3,v_4\},\{v_4,v_5\}\}$ and $\mathcal{B}_2(\{C_5\})=\{\{v_1,v_3\},\{v_1,$ $v_4\}, \{v_2,v_4\},$ $\{v_2,v_5\},\{v_3,v_5\}\}$, i.e. $\mathcal{B}_1(\{C_5\}) \cap \mathcal{B}_2(\{C_5\}) = \emptyset$. Moreover, the vertex $v_3$ satisfies $\{v_2,v_4\} \subseteq N_{P_5}(v_3)$ and $\{v_2,v_4\} \subseteq N_{C_5}(v_3)$, so $\zeta (\mathcal{H})=1$ for every non-empty subfamily $\mathcal{H} \subseteq \mathcal{H}_5$.

Additionally, consider the family $\mathcal{H}_{ex}^{(n)}=\{H_1,H_2,H_3,H_4\}$ depicted in Fig. 4. $\mathcal{H}_{ex}^{(n)}$ is defined on the common vertex set $V=\{v_1,\ldots ,v_n,v_{n+1},\ldots ,$ $v_{n+6}\}$, $n \ge 7$, $n \mod 5 \in \{0,2,4\}$, and the dashed lines in the figure indicate that $H_i$ differs from $H_j$ in the fact of containing, or not, each one of the edges $v_1v_n$ and $v_{n+2}v_{n+4}$. Let $V_1=\{v_1,\ldots ,v_n\}$ and $V_2=\{v_{n+1},\ldots ,v_{n+6}\}$. We have that, for every $H \in \mathcal{H}_{ex}^{(n)}$, $\langle V_1 \rangle _H \cong P_n$ or $\langle V_1 \rangle _H \cong C_n$. In consequence, for every non-empty subfamily $\mathcal{H} \subseteq \mathcal{H}_{ex}^{(n)}$, we have that ${\text {Sd}}_A(\mathcal{H})=\dim _A(P_n)+2=\dim _A(C_n)+2$, and every simultaneous adjacency basis B has the form $B=B' \cup X$, where $X \subset V_2$ and $B'$ is a simultaneous adjacency basis of $\mathcal{H}'=\{\langle V_1 \rangle _{H} :\; H \in \mathcal{H}\}$. Moreover, we have that $\mathcal{B}_1(\mathcal{H})=\{B' \cup X\}$, where $B'$ is a simultaneous adjacency basis of $\mathcal{H}'$ that is also a dominating set of every $H' \in \mathcal{H}'$ (Lemma 2, and the fact that two graphs in $\mathcal{H}'$ differ at most in the fact of containing, or not, the edge $v_1v_n$, guarantee the existence of such $B'$) and $X \in \{\{v_{n+2},v_{n+3}\},\{v_{n+3},v_{n+4}\},\{v_{n+3},v_{n+5}\},\{v_{n+3},v_{n+6}\},\{v_{n+5},v_{n+6}\}\}$. Finally, $\mathcal{B}_2(\mathcal{H})=\{B' \cup \{v_{n+2},v_{n+4}\}\}$, where $B'$ is a simultaneous adjacency basis of $\mathcal{H}'$ that is also a dominating set of every $H' \in \mathcal{H}'$. Clearly, $\mathcal{B}_1(\mathcal{H}) \cap \mathcal{B}_2(\mathcal{H})=\emptyset$. Moreover, for every $B \in \mathcal{B}_2(\mathcal{H})$, the vertex $v_{n+1}$ satisfies $B \subseteq N_{H}(v_{n+1})$ for every $H \in \mathcal{H}$, so $\zeta (\mathcal{H})=1$.

Fig. 4

For $n \ge 7$, $n \mod 5 \in \{0,2,4\}$, every non-empty subfamily $\mathcal{H}$ of the family $\mathcal{H}_{ex}^{(n)}=\{H_1,H_2,H_3,H_4\}$ satisfies $\mathcal{B}_1(\mathcal{H}) \cap \mathcal{B}_2(\mathcal{H})=\emptyset$ and $\zeta (\mathcal{H})=1$

The aforementioned facts, along with Corollaries 10 and 11, allows us to obtain examples where Eq. 3 becomes an equality.

Proposition 7

Let $\mathcal{G}=\{G_1,G_2,\ldots ,G_k\}$ be a family composed by path or cycle graphs on a common vertex set $V_1$ of size $p \ge 4,$ and let $\{K_t,N_t\}$ be a family composed by a complete and an empty graph on a common vertex set $V_2$ of size $t \ge 2$. Let $\mathcal{G}' \subseteq \{N_t+G_1,N_t+G_2,\ldots ,N_t+G_k\},$ $\mathcal{G}'\ne \emptyset ,$ and let $\mathcal{G}'' \subseteq \{K_{n+t}, K_t+G_1,K_t+G_2,\ldots ,K_t+G_k\},$ $\mathcal{G}''\ne \emptyset .$ Then,  the following assertions hold : 

• (i) For every non-empty subfamily $\mathcal{H} \subseteq \mathcal{H}_5,$

  $$\begin{aligned} {\text {Sd}}((\mathcal{G}' \cup \mathcal{G}'') \circ \mathcal{H})=|V_1 \cup V_2|\cdot {\text {Sd}}_A(\mathcal{H})+|V_M(\mathcal{G}' \cup \mathcal{G}'')|=2p+3t. \end{aligned}$$

• (ii) For every $n \ge 7,$ where $n \mod 5 \in \{0,2,4\},$ and every non-empty subfamily $\mathcal{H} \subseteq \mathcal{H}_{ex}^{(n)},$

  $$\begin{aligned} {\text {Sd}}((\mathcal{G}' \cup \mathcal{G}'')\circ \mathcal{H})= & {} |V_1 \cup V_2|\cdot {\text {Sd}}_A(\mathcal{H})+|V_M(\mathcal{G}' \cup \mathcal{G}'')|\\= & {} (p+t)\cdot \left( \left\lfloor \frac{2n+2}{5}\right\rfloor +2\right) +t. \end{aligned}$$

Proposition 8

Let G be a connected graph of order q such that $\overline{G}$ is connected. Then,  the following assertions hold : 

• (i) For every non-empty subfamily $\mathcal{H} \subseteq \mathcal{H}_5,$

  $$\begin{aligned} {\text {Sd}}(\{G,\overline{G}\} \circ \mathcal{H})=q\cdot {\text {Sd}}_A(\mathcal{H})+|V_M(\{G,\overline{G}\})|=2q+|V_T(G)|+|V_F(G)|. \end{aligned}$$

• (ii) For every $n \ge 7,$ where $n \mod 5 \in \{0,2,4\},$ and every non-empty subfamily $\mathcal{H} \subseteq \mathcal{H}_{ex}^{(n)},$

  $$\begin{aligned} {\text {Sd}}(\{G,\overline{G}\}\circ \mathcal{H})= & {} q\cdot {\text {Sd}}_A(\mathcal{H})+|V_M(\{G,\overline{G}\})|\\= & {} q\cdot \left( \left\lfloor \frac{2n+2}{5}\right\rfloor +2\right) +|V_T(G)|+|V_F(G)|. \end{aligned}$$

The previous examples additionally show that the bounds of Eq. 3 are tight. In general, the upper bound is reached when $\min \{\vert S_1 \vert ,\vert S_2 \vert ,\vert S_3 \vert \}=\vert S_3 \vert$ or when for every $B_1 \in \mathcal{B}_1(\mathcal{H})$ there exist exactly $k_2$ vertices $v_{p_1},v_{p_2},\ldots ,$ $v_{p_r} \in V_2-B_1$ such that $B_1 \cap N_{H}(v_{p_i})=\emptyset$ for some $H \in \mathcal{H}$ and for every $B_2 \in \mathcal{B}_2(\mathcal{H})$ there exist exactly $k_2$ vertices $v_{q_1},v_{q_2},\ldots ,v_{q_s} \in V_2-B_2$ such that $B_2 \subseteq N_{H}(v_{q_i})$ for some $H \in \mathcal{H}$.

In order to present our next results, we introduce some additional definitions. For a family $\mathcal{H}$ of non-trivial graphs on a common vertex set V, and a simultaneous adjacency basis $B \in \mathcal{B}(\mathcal{H})$, consider the sets

$$\begin{aligned} P(B)=\{v \in V :\; B \subseteq N_{H}(v) \text { for some } H \in \mathcal{H}\} \end{aligned}$$

and

$$\begin{aligned} Q(B)=\{v \in V :\; B \cap N_{H}(v)=\emptyset \text { for some } H \in \mathcal{H}\}. \end{aligned}$$

Based on the definitions of P(B) and Q(B), we define the parameter

$$\begin{aligned} \xi (G,\mathcal{H})=\underset{B \in \mathcal{B}(\mathcal{H})}{\min }\left\{ \vert P(B)\vert \left( \vert V_T(G)\vert -\vert T(G)\vert \right) +\vert Q(B)\vert \left( \vert V_F(G)\vert -\vert F(G)\vert \right) \right\} . \end{aligned}$$

Finally, for a graph G, let $V'_T(G)=\bigcup _{v^* \in T(G)}(v^*-\{v\})$ be the set composed by all vertices, except one, from every true twin equivalence class of G. Likewise, let $V'_F(G)=\bigcup _{v^* \in F(G)}(v^*-\{v\})$ be the set composed by all vertices, except one, from every false twin equivalence class of G. For convenience, we will assume without loss of generality that for every graph G a fixed vertex will always be the one excluded from every true or false twin equivalence class when constructing $V'_T(G)$ or $V'_F(G)$, respectively. With these definitions in mind, we give our next result.

Theorem 13

Let G be a connected graph of order n and let $\mathcal{H}=\{H_1,H_2,\ldots ,$ $H_k\}$ be a family of non-trivial graphs on a common vertex set $V_2.$ If for every simultaneous adjacency basis B of $\mathcal{H}$ there exists $H \in \mathcal{H}$ where one vertex v satisfies $B \subseteq N_{H}(v),$ or there exists $H' \in \mathcal{H}$ for which B is not a dominating set,  then

$$\begin{aligned} n\cdot {\text {Sd}}_A(\mathcal{H})\le {\text {Sd}}(G \circ \mathcal{H}) \le n\cdot {\text {Sd}}_A(\mathcal{H})+ \xi (G,\mathcal{H}). \end{aligned}$$

Proof

${\text {Sd}}(G \circ \mathcal{H})\ge n\cdot {\text {Sd}}_A(\mathcal{H})$ by Theorem 11, so we only need to prove that ${\text {Sd}}(G \circ \mathcal{H}) \le n\cdot {\text {Sd}}_A(\mathcal{H})+ \xi (G,\mathcal{H})$. Let B be a simultaneous adjacency basis of $\mathcal{H}$ for which $\xi (G,\mathcal{H})$ is obtained. We differentiate the following cases for every graph $H_i \in \mathcal{H}$:

• 1. There exist $w_1,w_2 \in V_2$ such that $B \subseteq N_{H_i}(w_1)$ and $B \cap N_{H_i}(w_2)=\emptyset$. In this case, we define the set $S_i=(V(G) \times B)\cup (V'_T(G) \times \{w_1\})\cup (V'_F(G) \times \{w_2\})$.

• 2. There exists $w_1 \in V_2$ such that $B \subseteq N_{H_i}(w_1)$ and there exists no vertex $x\in V_2$ such that $B \cap N_{H_i}(x)=\emptyset$. In this case, we define the set $S_i=(V(G) \times B) \cup (V'_T(G) \times \{w_1\})$.

• 3. There exists $w_2 \in V_2$ such that $B \cap N_{H_i}(w_2)=\emptyset$ and there exists no vertex $x\in V_2$ such that $B \subseteq N_{H_i}(x)$. In this case, we define the set $S_i=(V(G) \times B) \cup (V'_F(G) \times \{w_2\})$.

• 4. There exists no vertex $x\in V_2$ such that $B \subseteq N_{H_i}(x)$ or $B \cap N_{H_i}(x)=\emptyset$. In this case, we define the set $S_i=V(G) \times B$.

For cases 1, 2 and 3, it is shown in [12] that the corresponding set $S_i$ is a metric generator for $G \circ H_i$. Moreover, as we discussed in the proof of Theorem 12, in case 4 the corresponding set $S_i$ is a metric generator for $G \circ H_i$. In consequence, the set $S=\bigcup _{1\le i \le k}S_i$ is a simultaneous metric generator for $G \circ \mathcal{H}$. Therefore, ${\text {Sd}}(G \circ \mathcal{H}) \le \vert S \vert = n\cdot {\text {Sd}}_A(\mathcal{H})+ \xi (G,\mathcal {H})$, so the result holds.

The bounds of the inequalities in Theorem 13 are tight. As pointed out in [12], a twins-free graph G satisfies $T(G)=V_T(G)=F(G)=V_F(G)=\emptyset$. In consequence, $\xi (G,\mathcal{H})=0$ for any twins-free graph G and any graph family $\mathcal{H}$, so Theorem 13 leads to the next result.

Proposition 9

Let G be a twins-free connected graph of order n,  and let $\mathcal{H}$ be a family of non-trivial graphs on a common vertex set. Then, 

$$\begin{aligned} {\text {Sd}}(G\circ \mathcal{H})=n\cdot {\text {Sd}}_A(\mathcal{H}). \end{aligned}$$

Recall the families $\mathcal{K}(V)$ of star graphs defined in Sect. 2. The following result is an example of a family for which the upper bound of the inequalities of Theorem 13 is reached.

Proposition 10

For every finite set V of size $|V|\ge 4,$ ${\text {Sd}}(P_2 \circ \mathcal{K}(V))=2\cdot |V|-1.$

Proof

By Corollary 2, every simultaneous adjacency basis B of $\mathcal{K}(V)$ has the form $V-\{v_i\}$, $i \in \{1,\ldots ,|V|\}$. In $K_{1,n-1}^i$, we have that $B \subseteq N_{K_{1,n-1}^i}(v_i)$, so $\xi (P_2,\mathcal{K}(V))=1$. Thus, ${\text {Sd}}(P_2 \circ \mathcal{K}(V)) \le 2 \cdot {\text {Sd}}_A(\mathcal{K}(V))+1=2 \cdot |V|-1$. Additionally, since $P_2 \circ H \cong H+H$ for any graph H, we have that ${\text {Sd}}(P_2 \circ \mathcal{K}(V))={\text {Sd}}(\mathcal{K}(V)+\mathcal{K}(V)) \ge 2\cdot {\text {Sd}}_A(\mathcal{K}(V))+1=2\cdot |V|-1$ by Theorem 8, so the equality holds.

As we did for join graphs, now we define large families composed by subgraphs of a lexicographic product graph $G \circ H$, which may be seen as the result of a relaxation of the lexicographic product operation, in the sense that not every pair of nodes from two copies of the second factor corresponding to adjacent vertices of the first factor must be linked by an edge. Since for any adjacency basis B of $G \circ H$, the family $\mathcal{R}_B$ defined in the next result is a subfamily of $\mathcal{G}_B(G \circ H)$, the result follows directly from Theorem 2.

Corollary 12

Let G be a connected graph of order n,  let H be a non-trivial graph and let B be an adjacency basis of $G \circ H$. Let $E'=\{(u_i,u_j)(u_r,u_s) \in E(G \circ H) :\; i \ne r, (u_i,u_j) \notin B, (u_r,u_s) \notin B\}$ and let $\mathcal{R}_B=\{R_1,R_2,\ldots ,R_k\}$ be a graph family,  defined on the common vertex set $V(G \circ H),$ such that,  for every $l \in \{1,\ldots ,k\},$ $E(R_l)=E(G \circ H)-E_l,$ for some edge subset $E_l \subseteq E'.$ Then, 

$$\begin{aligned} {\text {Sd}}(\mathcal{R}_B) \le \dim (G \circ H). \end{aligned}$$

5 Concluding Remarks

In this paper we introduced the notion of simultaneous adjacency dimension of graph families. We studied its properties, as well as its relationship to the simultaneous metric dimension. In particular, we obtained the exact value, or sharp bounds, for this parameter on some families. Additionally, we showed how, given an adjacency basis B of a graph, large graph families can be constructed having B as a simultaneous adjacency basis.

The simultaneous adjacency dimension proved useful for studying the simultaneous metric dimension of families composed by lexicographic product graphs. From a general definition of lexicographic product, we focused on two particular cases, namely join graphs and standard lexicographic product graphs. We obtained relations between the simultaneous metric dimension of families composed by lexicographic product graphs and the simultaneous adjacency dimension of families composed by the second factors. In several cases, these relations allowed us to obtain the exact value of the simultaneous metric dimension for a large number of graph families composed by lexicographic product graphs.