Graphs with the edge metric dimension smaller than the metric dimension ^††footnotetext: [email protected], [email protected], [email protected], [email protected], and
      [email protected]

Let $S$ be a metric basis of $G_{n_{1},n_{2},n_{3}}$. If $S$ does not contain a vertex of the subgraph $G_{n_{1},n_{2}}$, then $r(a_{2}|S)=r(a_{n_{1}}|S)$. Thus, $S$ contains at least one vertex of $G_{n_{1},n_{2}}$. Moreover, if $S$ does not contain two pendant vertices $j_{r}$ and $j_{t}$ attached to $i$, then $r(j_{r}|S)=r(j_{t}|S)$. Thus, $S$ contains at least $n_{3}-1$ pendant vertices attached to $i$, and so, in conclusion we get $\dim(G_{n_{1},n_{2},n_{3}})\geq n_{3}$.

Now let $T$ be an edge metric basis. Here the situation is analogous since $r(a_{1}a_{2}|T)=r(a_{1}a_{n_{1}}|,T)$ if $T$ does not contain a vertex of $G_{n_{1},n_{2}}$, and $r(j_{r}i|T)=r(j_{t}i|T)$ if $j_{r}$ and $j_{t}$ are pendant vertices attached to $i$ and not in $T$. ∎

Let $S=\{j_{1},j_{2},\dots,j_{n_{3}-1},a_{\alpha},a_{\beta}\}$, where $\alpha=\lfloor\frac{n_{1}+1}{2}\rfloor$ and $\beta=\lceil\frac{n_{1}+3}{2}\rceil$. Observe that $d(a_{1},a_{\alpha})=d(a_{1},a_{\beta})$ since $d(a_{1},a_{\alpha})=\lfloor\frac{n_{1}+1}{2}\rfloor-1$ and $d(a_{1},a_{\beta})=n_{1}+1-\lceil\frac{n_{1}+3}{2}\rceil$. Moreover, $d(a_{\alpha},a_{\beta})=1$ if $n_{1}$ is odd and $d(a_{\alpha},a_{\beta})=2$ otherwise. Obviously, $S$ contains $n_{3}+1$ vertices. And since $n_{1}\geq 5$, we have $\beta<n_{1}$. Denote $\gamma=d(a_{\alpha},a_{1})=\lfloor\frac{n_{1}-1}{2}\rfloor$.

First we show that $S$ is a metric generator of $G_{n_{1},n_{2},n_{3}}$. Since $n_{3}\geq 2$, there is a vertex of $S$ outside the subgraph $G_{n_{1},n_{2}}$. This vertex distinguishes those vertices of $G_{n_{1},n_{2}}$ which are at different distances from $a_{1}$, but not those which are at the same distance from $a_{1}$. According to the distance from $a_{1}$, the vertices of $G_{n_{1},n_{2}}$ are partitioned into nontrivial sets $\{a_{2},a_{n_{1}}\}$, $\{a_{3},a_{n_{1}-1},b_{1},c\}$, $\{a_{4},a_{n_{1}-2},b_{2}\}$, etc. Some of these sets are probably smaller since they do not need to contain vertices of both $C$ and $P$, and $n_{1}$ could be even.

Let $\delta=\lfloor\frac{n_{1}}{2}\rfloor$. For every $v\in V(G_{n_{1},n_{2}})$, denote $\tilde{r}(v)=(d(v,a_{\alpha}),d(v,a_{\beta}))$. Then the vertices in the first set of the partition have $\tilde{r}(a_{2})=(\gamma-1,\delta)$ and $\tilde{r}(a_{n_{1}})=(\delta,\gamma-1)$. Since $\gamma\leq\delta$, these pairs are different. Further, the pairs $\tilde{r}$ for vertices in the second set of the partition are $(\gamma-2,\delta-1)$, $(\delta-1,\gamma-2)$, $(\gamma,\delta+1)$, $(\delta+1,\gamma)$, and they are pairwise distinct too. Since the distances to vertices of $C$ decrease while the distances to vertices of $P$ increase, it is obvious that the pair $a_{\alpha},a_{\beta}$ distinguishes the vertices in the sets of the partition. Hence, $S$ identifies the vertices of $G_{n_{1},n_{2}}$.

Since a pendant vertex in $S$ is identified trivially, it remains to check the vertices $i$ and $j_{n_{3}}$. Obviously, $j_{n_{3}}$ is the only vertex at distance $2$ from the pendant vertices in $S$ and at distance $\gamma+2$ from $a_{\alpha}$. On the other hand, $i$ is the only vertex at distance $1$ from the pendant vertices in $S$. Thus, $S$ is a metric generator of $G_{n_{1},n_{2},n_{3}}$.

Now we show that $S$ is an edge metric generator of $G_{n_{1},n_{2},n_{3}}$. We proceed analogously as in the case for the metric generator. According to the distance from $a_{1}$, the vertices of $S$ outside $G_{n_{1},n_{2}}$ partition the edges of $G$ into sets $\{a_{1}a_{2},a_{1}a_{n_{1}}\}$, $\{a_{2}a_{3},a_{n_{1}}a_{n_{1}-1},a_{2}b_{1},a_{n_{1}}c\}$, $\{a_{3}a_{4},a_{n_{1}-1}a_{n_{1}-2},b_{1}b_{2}\}$, etc. Again, some of these sets are probably smaller since they do not need to contain the edges of both $C$ and $P$, and $n_{1}$ may be odd. For every $e\in E(G_{n_{1},n_{2},n_{3}})$, denote $\tilde{r}(v)=(d(e,a_{\alpha}),d(e,a_{\beta}))$. Then the pairs $\tilde{r}$ for edges in the first set of the partition are $(\gamma-1,\gamma)$ and $(\gamma,\gamma-1)$. Further, the pairs $\tilde{r}$ for edges in the second set of the partition are $(\gamma-2,\delta-1)$, $(\delta-1,\gamma-2)$, $(\gamma-1,\delta)$, $(\delta,\gamma-1)$ and they are pairwise distinct too. Since the distances to edges of $C$ decrease while the distances to edges of $P$ increase, it is obvious that the pair $a_{\alpha},a_{\beta}$ distinguishes the edges in the sets of the partition. Hence, $S$ identifies the edges of $G_{n_{1},n_{2}}$.

Since a pendant edge $ij_{t}$ is identified trivially if $j_{t}\in S$, it remains to check the edges $ia_{0}$ and $ij_{n_{3}}$. Obviously, $ij_{n_{3}}$ is the only edge at distance $1$ from the pendant vertices in $S$ and at distance $\gamma+1$ from $a_{\alpha}$. On the other hand, $ia_{1}$ is the only edge at distance $1$ from the pendant vertices in $S$ and at distance $\gamma$ from $a_{\alpha}$. Therefore, $S$ is a metric generator of $G_{n_{1},n_{2},n_{3}}$ and the proof is completed. ∎

First assume that $n_{1}$ is odd. Analogously as in the proof of Lemma 4, let $\alpha=\lfloor\frac{n_{1}+1}{2}\rfloor$, $\gamma=\lfloor\frac{n_{1}-1}{2}\rfloor$ and $\delta=\lfloor\frac{n_{1}}{2}\rfloor$. Since $n_{1}$ is odd, $\gamma=\delta$. As shown in Observation 3, every metric basis of $G_{n_{1},n_{2},n_{3}}$ contains a vertex outside $G_{n_{1},n_{2}}$. By using the distances, this vertex partitions $V(G_{n_{1},n_{2}})$ into nontrivial sets $P_{1}=\{a_{2},a_{n_{1}}\}$, $P_{2}=\{a_{3},a_{n_{1}-1},b_{1},c\}$, $P_{3}\subseteq\{a_{4},a_{n_{1}-2},b_{2}\}$, etc. For every $v\in V(G_{n_{1},n_{2}})$, we denote $\tilde{r}(v)=d(a_{\alpha},v)$. Then the values of $\tilde{r}$ for the vertices in $P_{1}$ are $\gamma-1$ and $\delta$, and they are different. The values of $\tilde{r}$ for vertices in $P_{2}$ are $\gamma-2$, $\delta-1$, $\gamma$ and $\delta+1$, and they are different too. The set $P_{3}$ contains vertices with values of $\tilde{r}$ being $\gamma-3$, $\delta-2$ and $\gamma+1$, etc. Hence, to identify the vertices of $G_{n_{1},n_{2}}$ it suffices (and is necessary by the proof of Observation 3) that a metric generator of $G_{n_{1},n_{2},n_{3}}$ will contain only one vertex of $G_{n_{1},n_{2}}$, namely $a_{\alpha}$. Hence, $\{j_{1},j-2,\dots,j_{n_{3}-1},a_{\alpha}\}$ is a metric generator of $G_{n_{1},n_{2},n_{3}}$, see the proof of Lemma 4. By Observation 3, we then get $\dim(G_{n_{1},n_{2},n_{3}})=n_{3}$.

We now assume $n_{1}$ is even and proceed analogously as above. Vertices outside $G_{n_{1},n_{2}}$ partition $V(G_{n_{1},n_{2},n_{3}})$ into nontrivial sets $P_{1}=\{a_{2},a_{n_{1}}\}$, $P_{2}=\{a_{3},a_{n_{1}-1},b_{1},c\}$, $P_{3}\subseteq\{a_{4},a_{n_{1}-2},b_{2}\}$, etc. We denote this partition by $\mathcal{P}$. (Though it is not obvious, this partition is slightly different from the partition for the case when $n_{1}$ is odd.) We show that there is not a unique vertex in $G_{n_{1},n_{2}}$ which distinguishes all the vertices inside the sets of $\mathcal{P}$. Let $v\in V(G_{n_{1},n_{2},n_{3}})$. By symmetry, it suffices to distinguish four cases:

Since the other possibilities are symmetric, every metric basis of $G_{n_{1},n_{2},n_{3}}$ contains at least two vertices of $G_{n_{1},n_{2}}$. And since every metric basis of $G_{n_{1},n_{2},n_{3}}$ contains at least $n_{3}-1$ pendant vertices attached to $i$, we have $\dim(G_{n_{1},n_{2},n_{3}})\geq n_{3}+1$. Thus, by Lemma 4, $\dim(G_{n_{1},n_{2},n_{3}})=n_{3}+1$. ∎

First assume that $n_{1}$ is odd. Since $n_{3}\geq 2$, every edge metric basis contains a vertex outside of $G_{n_{1},n_{2}}$, and by using distances, this vertex partitions $E(G_{n_{1},n_{2},n_{3}})$ into sets $P_{1}=\{a_{1}a_{2},a_{1}a_{n_{1}}\}$, $P_{2}=\{a_{2}a_{3},a_{n_{1}}a_{n_{1}-1},a_{2}b_{1},a_{n_{1}}c\}$, $P_{3}\subseteq\{a_{3}a_{4},a_{n_{1}-1}a_{n_{1}-2},b_{1}b_{2}\}$, etc. We show that there is no vertex in $G_{n_{1},n_{2},n_{3}}$ which distinguishes edges inside these sets. Let $v\in V(G_{n_{1},n_{2},n_{3}})$. By symmetry, it suffices to distinguish the following four situations.

Since the other possibilities are symmetric, every edge metric basis of $G_{n_{1},n_{2},n_{3}}$ contains at least two vertices of $G_{n_{1},n_{2}}$. And since also every edge metric basis of $G_{n_{1},n_{2},n_{3}}$ contains at least $n_{3}-1$ pendant vertices attached to $i$, we have ${\rm edim}(G_{n_{1},n_{2},n_{3}})\geq n_{3}+1$. By Lemma 4, we then have ${\rm edim}(G_{n_{1},n_{2},n_{3}})=n_{3}+1$.

Now assume that $n_{1}$ is even. Analogously to the proof of Lemma 4, let $\alpha=\lfloor\frac{n_{1}+1}{2}\rfloor$, $\gamma=\lfloor\frac{n_{1}-1}{2}\rfloor$ and $\delta=\lfloor\frac{n_{1}}{2}\rfloor$. Since $n_{1}$ is even, $\gamma=\delta-1$. The vertices of an edge metric basis outside $G_{n_{1},n_{2}}$ partition the edges of $G_{n_{1},n_{2},n_{3}}$ into sets $P_{1}=\{a_{1}a_{2},a_{1}a_{n_{1}}\}$, $P_{2}=\{a_{2}a_{3},a_{n_{1}}a_{n_{1}-1},a_{2}b_{1},a_{n_{1}}c\}$, $P_{3}\subseteq\{a_{3}a_{4},a_{n_{1}-1}a_{n_{1}-2},b_{1}b_{2}\}$, etc. For every $e\in E(G_{n_{1},n_{2},n_{3}})$, let us denote $\tilde{r}(e)=d(a_{\alpha},e)$. Then the values of $\tilde{r}$ for the edges in $P_{1}$ are $\gamma-1$ and $\gamma$ and they are different. The values of $\tilde{r}$ for edges in $P_{2}$ are $\gamma-2$, $\delta-1$, $\gamma-1$ and $\delta$ and they are different too. The values of $\tilde{r}$ for edges in $P_{3}$ are $\gamma-3$, $\delta-2$ and $\gamma$, etc. Hence, in order to identify the edges of $G_{n_{1},n_{2},n_{3}}$, it suffices (and it is indeed necessary by the proof of Observation 3) that an edge metric generator will contain only one vertex of $G_{n_{1},n_{2}}$, namely $a_{\alpha}$. Hence, the set $\{j_{1},j_{2},\dots,j_{n_{3}-1},a_{\alpha}\}$ is an edge metric generator of $G_{n_{1},n_{2},n_{3}}$, see the proof of Lemma 4. Therefore, by Observation 3, we get ${\rm edim}(G_{n_{1},n_{2},n_{3}})=n_{3}$. ∎

First observe that for every $z_{2}\in V(G_{2})$, the set $\big{(}S_{1}-\{v_{1}\}\big{)}\cup\{z_{2}\}$ identifies the vertices of $G_{1}$. Analogously, if $z_{1}\in V(G_{1})$, then the set $\big{(}S_{2}-\{v_{2}\}\big{)}\cup\{z_{1}\}$ identifies the vertices of $G_{2}$. Since $G_{1}$ and $G_{2}$ are not paths, $|S_{1}|\geq 2$ and $|S_{2}|\geq 2$. Hence, the set $S=S_{1}\cup S_{2}-\{v_{1},v_{2}\}$ identifies the vertices of $G_{1}$ and it also identifies the vertices of $G_{2}$. Thus, to conclude that $S$ is a metric generator, we just may need to consider a pair of vertices $x,y$ with $x\in V(G_{1})$ and $y\in V(G_{2})$.

By (2), $d_{G_{2}}(u_{2},v_{2})\geq d_{G_{2}}(u_{2},z)$ for every $z\in V(G_{2})$. Hence, for $y\in V(G_{2})$, we have $d_{G}(u_{2},v_{2})\geq d_{G}(u_{2},y)$, while for $x\in V(G_{1})$ it follows $d_{G}(u_{2},x)\geq d_{G}(u_{2},v_{2})+1$. Thus, clearly $d_{G}(u_{2},x)>d_{G}(u_{2},y)$. Since $u_{2}\in S$, we conclude that $S$ identifies all the vertices of $G$, and so it is a metric generator for $G$.

Now suppose that $S^{\prime}$ is a metric generator for $G$ such that $|S^{\prime}|<|S|$. Then either $|S^{\prime}\cap V(G_{1})|<|S_{1}|-1$ or $|S^{\prime}\cap V(G_{2})|<|S_{2}|-1$. In the first case $(S^{\prime}\cap V(G_{1}))\cup\{v_{1}\}$ identifies $G_{1}$ which contradicts $\dim(G_{1})=|S_{1}|$, while in the second case $(S^{\prime}\cap V(G_{2}))\cup\{v_{2}\}$ identifies $G_{2}$ which contradicts $\dim(G_{2})=|S_{2}|$. Consequently, such a set $S^{\prime}$ does not exist, and we obtain that $S$ is a metric basis for $G$, which means $\dim(G)=\dim(G_{1})+\dim(G_{2})-2$.

The situation for the edge metric basis is analogous. The only difference comes by noticing that we may need to consider the edge metric representation of the edge $v_{1}v_{2}$, that is $r(v_{1}v_{2}|S)$, but this is unique in $G$. Observe that if $z_{1}\in T_{1}-\{v_{1}\}$ and $z_{2}\in T_{2}-\{v_{2}\}$, then $d_{G}(z_{1},v_{1}v_{2})<d_{G}(z_{1},e_{2})$ and $d_{G}(z_{2},v_{1}v_{2})<d_{G}(z_{2},e_{1})$ for every $e_{1}\in E(G_{1})$ and $e_{2}\in E(G_{2})$. ∎

We only prove the result for the case when $n_{1}$ is odd, since the proof for the case when $n_{1}$ is even is in fact the same.

Let $\beta=\lceil\frac{n_{1}+3}{2}\rceil$. As shown in the proof of Lemma 5, $\dim(G_{n_{1},n_{2},n_{3}})=n_{3}$ and $S=\{j_{1},j_{2},\dots,j_{n_{3}-1},a_{\alpha}\}$ is a metric basis of $G_{n_{1},n_{2},n_{3}}$. By Lemma 6, ${\rm edim}(G_{n_{1},n_{2},n_{3}})=n_{3}+1$ and $T=\{j_{1},j_{2},\dots,j_{n_{3}-1},a_{\alpha},a_{\beta}\}$ is an edge metric basis of $G_{n_{1},n_{2},n_{3}}$. We first consider the graphs $G_{1}$ and $G_{2}$, in concordance with the construction of $L^{\ell}_{n_{1},n_{2},n_{3}}$. Now, for $i\in\{1,2\}$, denote the metric basis $S$ and an edge metric basis $T$ in $G_{i}$ by $S_{i}$ and $T_{i}$, respectively. Then $a_{\alpha}^{1}\in S_{1}\cap T_{1}$ and $j_{1}^{2},a_{\alpha}^{2}\in S_{2}\cap T_{2}$, and moreover, $d_{G_{2}}(a_{\alpha}^{2},j_{1})\geq d_{G_{2}}(a_{\alpha}^{2},z)$ for every $z\in V(G_{2})$. Hence, the graphs $G_{1}$ and $G_{2}$ satisfy the assumptions of Lemma 7. Thus, $L^{2}_{n_{1},n_{2},n_{3}}$ has metric dimension $n_{3}$ and edge metric dimension $n_{3}+2$. Moreover, $S=S_{1}\cup S_{2}-\{a_{\alpha}^{1},j_{1}^{2}\}$ is a metric basis of $L^{2}_{n_{1},n_{2},n_{3}}$ and $T=T_{1}\cup T_{2}-\{a_{\alpha}^{1},j_{1}^{2}\}$ is an edge metric basis of $L^{2}_{n_{1},n_{2},n_{3}}$, for which $a_{\alpha}^{2}\in S\cap T$.