Electronic Journal of Graph Theory and Applications

Mostafa Tavakoli^a, Meysam Korivand^b, Ahmad Erfanian^b, Gholamreza Abrishami^a, Edy Tri Baskoro^c

^aDepartment of Applied Mathematics, Faculty of Mathematical Sciences, Ferdowsi University of Mashhad, Mashhad, I. R. Iran

^bDepartment of Pure Mathematics and the Center of Excellnce in Analysis on Algebraic Structures, Ferdowsi University of Mashhad, Mashhad, I. R. Iran

^cCombinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung

m_tavakoli@um.ac.ir, mekorivand@gmail.com, erfanian@um.ac.ir, m4abrishami@gmail.com, ebaskoro@math.itb.ac.id

For an ordered subset \(S = \{v_1, \ldots, v_k\}\) of vertices in a connected graph G and an edge e' of G, the edge metric S-representation of e' = ab is the vector \(r_G^e(e'|S) = (d_G(e', v_1), \ldots, d_G(e', v_k))\), where \(d_G(e', v_i) = \min\{d_G(a, v_i), d_G(b, v_i)\}\). A dominant edge metric generator for G is a vertex cover S of G such that the edges of G have pairwise different edge metric S-representations. A dominant edge metric generator of smallest size of G is called a dominant edge metric basis for G. The size of a dominant edge metric basis of G is denoted by \(\operatorname{Ddim}_e(G)\) and is called the dominant edge metric dimension. In this paper, the concept of dominant edge metric dimension (DEMD for short) is introduced and its basic properties are studied. Moreover, NP-hardness of computing DEMD of connected graphs is proved. Furthermore, this invariant is investigated under some graph operations at the end of the paper.

Keywords: dominant edge metric generator, edge metric dimension, vertex cover Mathematics Subject Classification: 05C12, 05C76, 90C60

DOI: 10.5614/ejgta.2023.11.1.16

Received: 05 July 2022, Revised: 27 February 2023, Accepted: 20 March 2023.

1. Introduction

All graphs considered in this paper are connected and simple. For a graph G, a subset S of V (G) with the property that every vertex of G is uniquely determined by its distances from the members of S is called a generator of G. This parameter of graphs was first introduced by Slater in 1975 [10]. This topic has attracted a lot of attention because of its plenty of applications in modeling many real world problems. Some applications of this invariant in chemical problems and navigation of robots are stated in [4] and [8]. One who is interested in these applications may refer to [4] and [8] for more details. Moreover, some other versions of this parameter have been introduced. For instance, Okamoto, Crosse, Phinezy, and Zhang defined the local metric dimension of a graph in [9] and Kelenc, Tratnik, and Yero introduced the edge metric dimension of a graph in [7]. In the present paper, we study a new version of metric generator which is a combination of edge metric generator and vertex cover. The idea comes from [11] which gives a combination of (vertex) metric dimension and dominating set. Before stating this concept, we recall some definitions and notations. A vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. The smallest cardinality of a vertex cover is called the vertex cover number and is denoted by β. If u, v ∈ V (G), then dG(u, v) denotes the number of edges on a shortest u, v-path in G. Also, if u ∈ V (G) and vw ∈ E(G), then the distance between u and vw, denoted by dG(vw, u), is min{dG(u, v), dG(u, w)}.

For an ordered subset S = {v1, . . . , vk} of vertices in a connected graph G and a vertex u of V (G), the metric S-representation of u is the vector rG(u|S) = (dG(u, v1), . . . , dG(u, vk)). Also, for an edge e ′ of E(G), the edge metric S-representation of e ′ is the vector r e ^G(e ′ |S) = (dG(e ′ , v1), . . . , dG(e ′ , vk)).

A subset S of V^G is called metric generator for G if the vertices of G have pairwise different metric S-representations. A metric generator of the smallest order is a metric basis for G, its order being the metric dimension of G and denoted by dim(G).

A subset S of V (G) with the property that all the edges of G have pairwise different edge metric S-representations is called an edge metric generator for G. The edge metric generator of smallest size is said to be an edge metric basis for G, its order is named the edge metric dimension of G and denoted by dime(G) (see [7]).

Now, let us define the dominant edge metric dimension as follows.

A dominant edge metric generator for G is a vertex cover S of G such that the edges of G have pairwise different edge metric S-representations. A dominant edge metric generator of smallest order is a dominant edge metric basis for G, its order being the dominant edge metric dimension (DEMD for short) Ddime(G) of G. In the second section of this paper, NP-hardness of computing DEMD of connected graphs is proved. In section 3 we present some basic properties of DEMD. Finally, we devote ourselves to consider this invariant under some graph operations.

We remind that all notations and terminologies are standard here and taken mainly from the standard books of graph theory. For instance, as usual we denote the path, the cycle, the star, and the complete graph on n vertices by Pn, Cn, Sⁿ and Kn, respectively. Moreover, the complement of a graph G is a graph G^c on the same vertices such that two distinct vertices of G^c are adjacent if and only if they are not adjacent in G. For a nonempty set V ′ ⊆ V (G), the subgraph G[V ′ ] induced by V ′ is the subgraph of G whose vertex set is V ′ and whose edge set consists of all edges

of G which have both ends in V ′ .

2. Basic Results

In this section, we present basic results for the dominant edge metric dimension of graphs. We also give some bounds for Ddime(G) and |E(G)|, according to pendant vertices of a graph G and dominant edge metric dimension of G, respectively. It is obvious that for any graph G, max{β(G), dime(G)} ≤ Ddime(G). Moreover, if G is a graph with n vertices, then 1 ≤ Ddime(G) ≤ n − 1.

The next theorem gives some formulas for Ddime(G), when G is complete, complete multipartite, cycle and, path, and wheel. Wheel graph, denoted by Wn, is the graph obtained by the join of all vertices of Cⁿ with K1. The proof is straightforward and we omit here.

Theorem 2.1. For each positive integers n and m,

• (i) Ddime(Kn) = n − 1.
• (ii) Ddime(Kn,m) = n + m − 1.

(ii) \[\operatorname{Ddim}_{e}(C_{n}) = \begin{cases} 3, & \text{if } n = 4, \\ \lceil \frac{n}{2} \rceil, & \text{if } n \geq 3. \end{cases}\]

(iii) \[\operatorname{Ddim}_{e}(P_n) = \lfloor \frac{n}{2} \rfloor\].

(iv) \[\operatorname{Ddim}_{e}(W_{n}) = \begin{cases} 4, & \text{if } n = 2, \\ \lceil \frac{n}{2} \rceil + 1, & \text{if } n \geq 3. \end{cases}\]

The next theorem provides a characterization of all graphs with the dominant edge metric dimension equal to 1 or 2. First, let us define two graphs H¹ and H² as depicted in the following figure, which are necessary for our characterization.

Figure 1. Graphs H1(a) and H2(b).

Theorem 2.2. Let G be a graph. Then

(i) Ddime(G) = 1 if and only if G ∈ {P1, P2},

(ii) \(\mathrm{Ddim}_{e}(G) = 2\) if and only if \(G \in \{P_3, P_4, P_5, K_3, H_1, H_2\}\).

Proof. (i) The inequality \(\beta(G) \leq \mathrm{Ddim}_{\mathrm{e}}(G)\) implies that G is a star graph. Since \(\dim_{\mathrm{e}}(G) = 1\), the star graph G has not more than 2 vertices. Therefore G is isomorphic to \(P_1\) or \(P_2\). The converse is trivial.

(ii) Let N(a) denote the set of neighbours of vertex a. Since \(\beta(G) \leq Ddim_e(G) = 2\), we can consider two cases as follows.

Case 1. \(\beta(G) = 1\).

In this case \(G \cong S_n\), for a positive integer n. Let S be a dominant edge metric basis of G. We claim n=3. For a contradiction, assume that \(n \neq 3\). If \(n \leq 2\) then \(\mathrm{Ddim}_{\mathrm{e}}(G)=1\), a contradiction. If \(n \geq 4\), for covering edges of \(S_n\), the center of \(S_n\), say a, must be belongs to S. Now, there exist at least two pendant vertices b and c of \(S_n\) such that \(b, c \notin S\). Thus \(r_G^e(ba|V(G)) = r_G^e(ca|V(G))\), so we reach a contradiction. Therefore \(G \cong P_3\).

Case 2. \(\beta(G) = 2\).

Let \(a, b \in V(G)\) and \(S = \{a, b\}\) be a dominant edge metric basis of G. Since S is a vertex cover of G, hence for any vertex \(c \in V(G) \setminus \{a, b\}\), we have \(N(c) \subseteq \{a, b\}\). We partition the vertices of \(V(G) \setminus \{a, b\}\) into sets \(V_a\), \(V_b\), and \(V_{a,b}\), where, \(V_a = \{x \mid x \in V(G) \setminus \{a, b\} \text{ and } N(x) = \{a\}\}\), \(V_b = \{x \mid x \in V(G) \setminus \{a, b\} \text{ and } N(x) = \{b\}\}\), and \(V_{a,b} = \{x \mid x \in V(G) \setminus \{a, b\} \text{ and } N(x) = \{a, b\}\}\).

Now, we may have the following two subcases.

Subcase 2a. \(ab \in E(G)\).

We claim that \(|V_a| \leq 1\). On the contrary, assume that \(|V_a| \geq 2\). So, we can consider two distinct vertices x and y in \(V_a\). Thus \(r_G^e(xa|V(G)) = r_G^e(ya|V(G))\), a contradiction. In a similar way, we have \(|V_b| \leq 1\) and \(|V_{a,b}| \leq 1\).

First, assume that \(|V_{a,b}|=0\). If \(|V_a|=|V_b|=0\), then \(G\cong P_2\), which is impossible. Hence, at least one of \(V_a\) and \(V_b\) is a non-empty set. If exactly one of \(V_a\) and \(V_b\) is a non-empty set, then \(G\cong P_3\). If both of \(V_a\) and \(V_b\) is non-empty, thus \(G\cong P_4\).

Second, suppose that \(|V_{a,b}|=1\). By the same method as above, if \(|V_a|=|V_b|=0\), then \(G\cong K_3\). If exactly one of \(V_a\) and \(V_b\) is non-empty or both of \(V_a\) and \(V_b\) are non-empty, then \(G\cong H_1\) or \(G\cong H_2\), respectively.

Subcase 2b. \(ab \notin E(G)\).

Similar to the Subcase 2a, one can check that \(G \in \{P_3, P_4, P_5\}\).

The converse of the cases are trivial and the proof is completed.

Theorem 2.3. Let G be a graph with \(Ddim_e(G) = m\). Then

\[|E(G)| \le \sum_{i=1}^{m} i \binom{m}{i} + m(m-1)/2.\]

Proof. Let \(S = \{a_1, a_2, \dots, a_m\}\) be a dominant edge metric basis of G, and \(S_{a_i} := \{a_i u \in E(G) \mid u \in V(G) \setminus S\}\), for \(1 \leq i \leq m\). We claim that \(E(G) = \bigcup_{i=1}^m S_{a_i} \cup E(G[S])\). For this, it is enough to show that \(E(G) \subseteq \bigcup_{i=1}^m S_{a_i} \cup E(G[S])\). On the contrary, assume that there exists \(xy \in E(G)\) such that \(xy \notin \bigcup_{i=1}^m S_{a_i} \cup E(G[S])\). Hence \(x, y \notin S\), and so edge xy can not be covered by S, a contradiction.

On the other hand, for any \(u \in V(G) \setminus S\), we have \(N(u) \subseteq S\). Now, if there exist \(u, v \in V(G) \setminus S\), such that N(u) = N(v), then we can assume that \(a_1 \in N(u) = N(v)\). Thus we have \(r_G^e(a_1u|S) = r_G^e(a_1v|S)\), which means that any non-empty subset of vertices of S has at most one common neighbours in \(V(G) \setminus S\). Since the subsets of S of size S, can be chosen by \(\binom{m}{i}\) ways, and for any common neighbours of S vertices of S, S has S distinct edges, we conclude that

\[|\bigcup_{i=1}^m S_{a_i}| \le \sum_{i=1}^m i \binom{m}{i}.\]

Moreover, the induced subgraph G([S]), has at most m(m-1)/2 edges. Consequently

\[|\bigcup_{i=1}^{m} S_{a_i} \cup E(G[S])| \le \sum_{i=1}^{m} i \binom{m}{i} + m(m-1)/2,\]

and the proof is completed.

Theorem 2.4. Let G be a graph with \(|V(G)| \ge 3\) and m pendant vertices. Then \(m \le \mathrm{Ddim}_{\mathrm{e}}(G)\).

Proof. Let a be a pendant vertex and S be a dominant edge metric generator of G. Then there exists \(b \in V(G)\) such that \(a \sim b\), and b is not a pendant vertex. Now, a or b must belong to S, for covering edge ab. Without loss of generality, we may assume that \(b \in S\). If there is another pendant vertex, namely c, such that \(c \sim b\), then at least one of a or c must be belong to S, to satisfy condition \(r_G^e(ab|S) \neq r_G^e(cb|S)\). This means that for any pendant vertex of G, there exists at least one element of S. Therefore \(m \leq |S|\).

In the next theorem, we improve Theorem 4.1 in [14] state that, for any connected graph G of order n, if \(G^c\) has at least three components, then \(\dim_{\mathbf{e}}(G) = n - 1\).

Theorem 2.5. Let G be a graph and \(G^c\) be disconnected. Then \(\dim_e(G) = |V(G)| - 1\).

Proof. Let \(H_1, H_2, \ldots, H_m\) be connected components of \(G^c\), with \(m \geq 2\).

First, suppose that there is a component of \(G^c\), as \(H_1\), with \(|V(H_1)| \geq 2\). So we can assume \(v, u \in V(H_1)\), and \(w \in V(H_2)\). In G, vertices v and u (respectively w) adjacent to all vertices of components \(H_2, H_3, \ldots, H_m\) (respectively \(H_1, H_3, \ldots, H_m\)). Thus there exist edges vw and uw in G. Now, for every vertex \(a \in V(G) \setminus \{u, v, w\}\), we have \(d_G(vw, a) = d_G(uw, a) = 1\) and \(d_G(vw, w) = d_G(uw, w) = 0\). Hence \(r_G^e(vw|V(G) \setminus \{u, v\}) = r_G^e(uw|V(G) \setminus \{u, v\})\). This implies that \(\dim_e(G) = |V(G)| - 1\).

Finally, assume that all connected components \(H_1, H_2, \ldots, H_m\) have one vertex. Therefore \(G = K_{|V(G)|}\) and \(\dim_e(G) = |V(G)| - 1\).

Corollary 2.1. Let G be a graph and \(G^c\) be disconnected. Then \(Ddim_e(G) = |V(G)| - 1\).

3. DEMD Over Some Graph Products

As it is proved in section 2, computing DEMD of connected graphs is NP-hard. It is the reason why we use some graph products to obtain DEMD for some product graphs in this section.

Let G and H be two graphs. The corona product G ◦ H, is obtained by taking one copy of G and |V (G)| copies of H; and by joining each vertex of the i-th copy of H to the i-th vertex of G, where 1 ≤ i ≤ |V (G)| (see [13] for more details).

In the following theorem, we give a formula for DEMD of the corona product of two graphs G and H.

Theorem 3.1. Let G and H be two graphs. Then

\[\mathrm{Ddim}_{\mathrm{e}}(G \circ H) = |V(G)||V(H)|.\]

Proof. In what follows, for g ∈ V (G), we will use the notation H^g to denote the copy of H in G ◦ H corresponding to g. Let h ∈ V (H) and set S^h = V (G) ∪ (∪g∈^V (G)(V (H^g − h)) where H^g − h is the graph obtained from H^g by removing its vertex corresponding to h. It is clear that V (Hg)'s are disjoint for distinct g. Moreover, S^h is a dominant edge metric generator of G ◦ H and so Ddime(G ◦ H) ≤ |V (G)||V (H)|. Thus, it is sufficient to prove that Ddime(G ◦ H) ≥ |V (G)||V (H)|. To do this, let S ′ be a dominant edge metric generator of G ◦ H. Suppose, on the contrary that there exist two vertices h, h′ ∈ H^g such that h, h′ ∈/ S ′ . Thus,

\[d_{G\circ H}(gh,u)=d_{G\circ H}(gh',u)=\begin{cases} d_G(g,u), & \text{if } u\in V(G),\\ d_G(g,g')+1, & \text{if } u\in V(H_{g'}) \text{ and } g'\neq g, \end{cases}\]

for each u ∈ S ′ \ V (Hg); and dG◦H(gh, u) = dG◦H(gh′ , u) = 1 for each u ∈ S ′ ∩ V (Hg) which contradicts the choice of S ′ . Therefore, |S ′ ∩ Hg| ≥ |V (H)| − 1.

Now suppose that g /∈ S ′ and |S ′ ∩ V (Hg)| = |V (H)| − 1. In this case, g must be a member of S ′ , because S ′ is a vertex cover of G ◦ H. Therefore, |S ′ | ≥ |V (G)||V (H)|. This completes the proof.

Figure 2. P³ ◦ K² and its dominant edge metric generator which is colored with white.

By an inductive argument, one can derive the following implication of Theorem 3.1. The proof is very similar to the proof of Theorem 3.1 and we omit here.

Theorem 3.2. Let G1, . . . , Gⁿ be graphs. Then

\[\mathrm{Ddim}_{\mathrm{e}}(G_1 \circ G_2 \circ \cdots \circ G_n) = \prod_{i=1}^n |V(G_i)|.\]

The dominant edge metric dimension of graphs | M. Tavakoli et al.

Figure 3. T3,3.

Example 3.3. A Caterpillar is a tree in which all the vertices are within distance 1 of a central path [1]. These graphs were first studied in a series of papers by Harary and Schwenk. Then the graph Tl,t = P^l ◦ K¯ t is called a Caterpillar (see Figure 3). Therefore, by Theorem 3.1, we will have

\[\mathrm{Ddim}_{\mathrm{e}}(T_{l,t}) = lt.\]

One can easily check that dime(Tl,t) = l(t − 1). It shows that Ddime(G) − dime(G) could be increased to any arbitrary positive integer number. Thus, we can conclude that for every positive integers m and n with n ≥ m, there exists a graph G such that Ddime(G) = n and dime(G) = m. Note that if n > m, then we can choose l = n − m and take G = Tl,t for arbitrary positive integer t ≥ 1. Thus, by the above results, we will have Ddime(G) = Ddime(Tl,t) = lt and dime(G) = dime(Tl,t) = l(t − 1). Hence, n − m = Ddime(G) − dime(G) = lt − l(t − 1) = l as required. In the case that m = n, the graph G can be considered G = Kn+1 and so Ddime(G) = dime(G) = (n + 1) − 1 = n.

The edge corona G ⋄ H of graphs G and H is obtained by taking one copy of G and |E(G)| disjoint copies of H associated to the edges of G, and for every edge gg′ ∈ E(G) joining g and g ′ to every vertex of the copy of H associated to gg′ , see [5, 12] for more details.

The following theorem will state the exact value of DEMD of edge corona product of two graphs G and H.

Theorem 3.4. If G and H are two graphs, then

\[\mathrm{Ddim}_{\mathrm{e}}(G \diamond H) = |E(G)|(|V(H)| - 1) + |V(G)|.\]

Proof. For g ∈ V (G), the notation Hgg′ stands for the copy of H in G ⋄ H corresponding to edge gg′ ∈ E(G). Let h ∈ V (H) and set S^h = V (G)∪(∪g∈^V (G)V (H^g −h)) where Hgg′ −h is the graph obtained from Hgg′ by removing its vertex corresponding to h. One can easily check that S is a dominant edge metric generator of G⋄ H and so Ddime(G⋄ H) ≤ |E(G)|(|V (H)| −1) + |V (G)|. To prove Ddime(G ◦ H) ≥ |V (G)||V (H)|, let S ′ be a dominant edge metric generator of G ⋄ H. Suppose, by way of contradiction, there exist two vertices h, h′ ∈ Hgg′ such that h, h′ ∈/ S ′ . Thus,

\[d_{G\diamond H}(gh,u)=d_{G\diamond H}(gh',u)=\begin{cases} d_G(gg',u), & \text{if } u\in V(G),\\ d_G(gg',g''g''')+1, & \text{if } u\in V(H_{g''g'''}) \text{ and } gg'\neq g''g''', \end{cases}\]

for each u ∈ S ′ \ V (Hgg′); and dG⋄H(gh, u) = dG⋄H(gh′ , u) = 1 for each u ∈ S ′ ∩ V (Hgg′) which contradicts the choice of S ′ . Therefore,

\[|S' \cap (\bigcup_{gg' \in E(G))} V(H_{gg'})| \ge |E(G)|(|V(H)| - 1).\]

Now, suppose that h ∈ V (Hgg′) \ S ′ and |S ′ ∩ V (Hgg′)| = (|V (H)| − 1). Since S ′ is a vertex cover of G ⋄ H, then it must have at least two vertices of {g, g′ , h} for covering edges gh, g ′h and gg′ . Therefore, |S ′ | ≥ |E(G)|(|V (H)| − 1) + |V (G)| and the proof is completed.

Figure 4. P³ ⋄ K² and its dominant edge metric generator which is colored with white.

It is interesting to consider the dominant edge metric generator for some other kinds of product between two graphs. Of course, the proofs for some of them are very similar to the proof of Theorem 3.4. For instance, if G + H is the join of two graphs G and H, then we can state the following result. The proof can be obtained by a similar argument applied in Theorem 3.4 and it is not appeared here.

Theorem 3.5. Let G and H be two graphs. Then Ddime(G + H) = |V (G)| + |V (H)| − 1.

4. Complexity Issues

The edge metric dimension problem is the problem of determining the edge metric dimension of a given graph G. Recently, in [7], the authors proved that the decision version of the edge metric dimension problem is NP-complete on connected graphs. The problem of finding a minimum vertex cover is a classical optimization problem in computer science. Its decision version was one of Karp's 21 NP-complete problems and is therefore a classical NP-complete problem (see [6] for more details).

It is natural to ask whether our similar problem for the dominant edge metric dimension is NP-complete by knowing the NP-completeness of two problems mentioned on above. However, one does not immediately deduce that this problem is NP-complete. Indeed, our primary aim in this section is to present a detailed proof for the NP-completeness of our problem. First, let us start with the following decision problem.

DEMD problem: Let G be a connected graph of order n and r be a positive integer such that 1 ≤ r ≤ n − 1 where n ≥ 3. Is Ddime(G) ≤ r?

Recall that the DEMD problem is the decision version of the problem of computing Ddime(G) for a given connected graph G. Our proof for showing the NP-completeness of DEMD problem is based on a reduction from the minimum vertex cover problem for connected graphs. For more details on the reduction technique for proving the NP-completeness of a problem in general, we refer the reader to [3]. Now, we are in the position to prove that the DEMD problem is NPcomplete.

Theorem 4.1. The DEMD problem is NP-complete.

Proof. We first show that DEMD\(\in\) NP. Let \(\overline{G}\) be a connected graph of order \(\overline{n}\) and let \(\overline{S}\) be a subset of \(V(\overline{G})\). We are going to check that \(\overline{S}\) is a dominate edge metric generator of \(\overline{G}\). It is easy to see that there exists a polynomial-time algorithm that checks whether \(\overline{S}\) is a vertex cover for \(\overline{G}\). Similarly, verifying that \(\overline{S}\) is an edge metric generator of \(\overline{S}\) can be performed in polynomial time. Thus, DEMD\(\in\) NP.

To show NP-hardness, we give a reduction from the minimum vertex cover problem for connected graphs. Let G=(V,E) be a connected graph with \(V=\{v_1,v_2,\ldots,v_n\}\). We construct G'=(V',E') from G such a way that

\[V' = V \cup X \cup Y,\]
\[E' = E \cup E_1 \cup E_2,\]

where \(X = \{x_1, x_2, \dots, x_n\}\), \(Y = \{y_1, y_2, \dots, y_n\}\), \(E_1 = \{x_i y_i \mid 1 \le i \le n\}\) and \(E_2 = \{v_i x_i \mid 1 \le i \le n\}\). As an example, consider the graphs \(G_4\) and \(G_4\) as they are shown in Figure 5.

Figure 5. The graphs \(G_4\) and \(G'_4\).

We claim that \(\operatorname{Ddim}_{\operatorname{e}}(G') = \beta(G) + n\). Suppose \(B = \{b_1, b_2, \dots, b_{\beta(G)}\}\) is a vertex cover of minimum size of G and \(S = \{x_1, x_2, \cdots, x_n, b_1, b_2, \dots, b_{\beta(G)}\}\) is an ordered set. It is easy to see that S is a vertex cover for G'. Now, we claim that S is a dominant edge metric generator for G'. For this purpose, since S is a vertex cover, we need to show that S is an edge metric generator for G'. In order to show that the edges of G' have pairwise different edge metric S-representations, let \(e_1\) and \(e_2\) be two arbitrary distinct edges of G'. In what follows, \(r_G^e(e'|S)_i\) refers to the ith entry of \(r_G^e(e'|S)\).

We distinguish five cases as the following.

Case 1. \(e_1 \in E_1\).

Suppose \(e_1 = x_i y_i\) where \(i \in \{1, 2, \dots, n\}\). In this case, if \(e_2 = wz\) where \(w \neq x_i, w \neq y_i, z \neq x_i\) and \(z \neq y_i\), then \(r_{G'}^e(e_1|S)_i = 0\) and \(r_{G'}^e(e_2|S)_i \neq 0\), thus \(r_{G'}^e(e_1|S) \neq r_{G'}^e(e_2|S)\). Otherwise, without loss of generality, if \(w = x_i\), then \(z \neq y_i\) since \(e_1\) and \(e_2\) are distinct. Thus, \(z = v_i\), because \(x_i\) has only two adjacent vertices \(v_i\) and \(y_i\). Since G' has at least three vertices, there exists a vertex \(v_j\) such that \(i \neq j\). Therefore, \(d_{G'}(v_j, x_i) = d_{G'}(v_j, v_i) + 1\) and \(d_{G'}(v_j, y_i) = d_{G'}(v_j, v_i) + 2\) which implies that \(d_{G'}(e_2, v_j) < d_{G'}(e_1, v_j)\). Hence, \(r_{G'}^e(e_2|S)_j < r_{G'}^e(e_1|S)_j\). Therefore, \(r_{G'}^e(e_1|S) \neq r_{G'}^e(e_2|S)\).

Case 2. \(e_2 \in E_1\).

The proof of this case is similar to the proof of Case 1.

Case 3. \(e_1 \in E_2\).

Suppose \(e_1 = x_i v_i\) where \(i \in \{1, 2, ..., n\}\). In this case, if \(e_2 = wz\) where \(w \neq x_i\), \(w \neq v_i\), \(z \neq x_i\)

and \(z \neq v_i\), then \(r_{G'}^e(e_1|S)_i = 0\) and \(r_{G'}^e(e_2|S)_i \neq 0\), thus \(r_{G'}^e(e_1|S) \neq r_{G'}^e(e_2|S)\). Otherwise, without loss of generality, if \(w = v_i\), then since \(e_1\) and \(e_2\) are distinct, we should have \(z \neq x_i\). Thus, \(z \in V(G)\). Suppose that \(z = v_j\) for some \(j \in \{1, 2, \dots, n\}\). Then \(d_{G'}(e_2, x_j) = 1\) and \(d_{G'}(e_1, x_j) = 2\). Therefore, \(r_{G'}^e(e_1|S) \neq r_{G'}^e(e_2|S)\).

Case 4. \(e_2 \in E_2\).

The proof of this case is similar to the proof of Case 3.

Case 5. \(\{e_1, e_2\} \subset E(G)\).

Suppose \(e_1 = v_s v_t\) and \(e_2 = v_r v_q\) where \(\{s, t, r, q\} \subset \{1, 2, \ldots, n\}\). Since \(e_1\) and \(e_2\) are two distinct edges, without loss of generality, suppose that \(v_s \neq v_r\). Therefore, \(d_{G'}(e_1, x_r) > 1\) and \(d_{G'}(e_2, x_r) = 1\). Thus, \(r_{G'}^e(e_1|S)_r > 1\) and \(r_{G'}^e(e_2|S)_r = 1\). Hence, \(r_{G'}^e(e_1|S) \neq r_{G'}^e(e_2|S)\).

In each of the above five cases, we have \(r_{G'}^e(e_1|S) \neq r_{G'}^e(e_2|S)\). Since \(e_1\) and \(e_2\) were chosen arbitrarily from E', it indicates that the edges of G' have pairwise different edge metric S-representations. Now, we claim that \(\operatorname{Ddim}_e(G') = |S|\). Suppose on the contrary that there is a dominant edge metric generator S' of G' such that |S'| < |S|. Since S' is a vertex cover for G', every edge \(x_iy_i\) is covered by S' for \(1 \leq i \leq n\). Hence \(x_i \in S'\) or \(y_i \in S'\). The graph G' has n edges \(x_iy_i\) for \(1 \leq i \leq n\) which they have no vertex in common. Therefore, the subgraph G of G' is covered by S' with at most w vertices where w = |S'| - n. On the other hand, \(|S| = \beta(G) + n\). Thus, \(w = |S'| - n < |S| - n = \beta(G)\). Hence, G is covered by at most W vertices such that \(W < \beta(G)\). But this contradicts the minimality of \(\beta(G)\). Therefore, \(\operatorname{Ddim}_e(G') = |S| = \beta(G) + n\).

It is easy to see that constructing G' from G can be done in polynomial time. Therefore, if there exists a polynomial-time algorithm for computing \(\mathrm{Ddim}_{\mathrm{e}}(G')\) then there exists a polynomial-time algorithm for computing \(\beta(G)\).

The well known theorem in graph theory, König's theorem, states that, in any bipartite graph, the number of edges in a maximum matching is equal to the number of vertices in a minimum vertex cover. We recall that maximum matchings can be found in polynomial time for any graph. Thus, the proof of Theorem 4.1 does not apply for proving the NP-compleness of the DEMD problem on bipartite graphs. Therefore, there is an interesting question about the complexity of this new problem. We leave it as the following open question.

Problem A. Let G be a connected bipartite graph G of order n and r be a positive integer such that \(1 \le r \le n-1\) where \(n \ge 3\). Is \(\mathrm{Ddim}_{\mathrm{e}}(G) \le r\)?

Open Problem. Is the problem A NP-complete?

The classical metric dimension problem can be formulated as an Integer Linear Programming (ILP) problem [2]. Also, there exists a simple ILP model for the vertex cover problem. Motivated by the previous results for the similar problems, we consider here an ILP model for computing \(\mathrm{Ddim}_{\mathrm{e}}(G)\) for a given connected graph G. We note that our model is based on the ILP model introduced in [2] for the classical metric dimension problem. So we have maintained as far as possible the terminology and notation of [2] for our new ILP model. Let G = (V, E) be a connected graph of order n where \(V = \{v_1, v_2, \ldots, v_n\}\). Let \(D' = [d'_{ij}]\) be an m by n matrix where m = |E| such that \(d'_{ij} = d_G(e_i, v_j)\) for \(i \in \{1, 2, \ldots, m\}\) and \(j \in \{1, 2, \ldots, n\}\) where \(e_i \in E\) and \(v_j \in V\). Consider the binary decision variables \(x_i\) for \(i \in \{1, 2, \ldots, n\}\) where \(x_i \in \{0, 1\}\). By \(x_i = 1\), we

mean the vertex vⁱ is on a dominant edge metric generator for G and xⁱ = 0 otherwise. We define the objective function F as follow.

\[F(x_1, x_2, \dots, x_n) = x_1 + x_2 + \dots + x_n.\]

Minimizing F subject to the mn constraints

\[|d'_{i1} - d'_{j1}|x_1 + |d'_{i2} - d'_{j2}|x_2 + \dots + |d'_{in} - d'_{jn}|x_n > 0,\]

such that eⁱ ∈ E and v^j ∈ V for i ∈ {1, 2, . . . , m} and j ∈ {1, 2, . . . , n}, and also m constraints

\[x_t + x_k > 0,\]

such that vtv^k ∈ E for {t, k} ⊆ {1, 2, . . . , n} is equivalent to finding a dominant edge metric generator of G.

Acknowledgment

The fifth author has been supported by the 2023 PPMI research grant, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Indonesia.

References

• [1] S. El-Basil, Caterpillar(Gutman) trees in chemical graph theory, Topics in Current Chemistry 153 (1990), 273–289.
• [2] G. Chartrand, L. Eroh, M.A. Johnson, and O.R. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math. 105 (2000), 99-113.
• [3] T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, Introduction to Algorithms, McGraw-Hill book company, The MIT Press, second edition, 2003.
• [4] M. Johnson, Structure-activity maps for visualizing the graph variables arising in drug design, J. Biopharm. Stat. 3 (1993), 203–236.
• [5] Y. Hou and W-C. Shiu, The spectrum of the edge corona of two graphs, Electron. J. Lin. Alg. 20 (2010), 586–594.
• [6] R.M. Karp, Reducibility among combinatorial problems. Complexity of Computer Computations. Springer, Boston, MA, (1972), 85–103.
• [7] A. Kelenc, N. Tratnik, and I.G. Yero, Uniquely identifying the edges of a graph: the edge metric dimension, Discrete Appl. Math. 256 (2018), 204–220.
• [8] S. Khuller, B. Raghavachari, and A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math. 70 (1996), 217–229.

• [9] F. Okamoto, L. Crosse, B. Phinezy, and P. Zhang, The local metric dimension of a graph, Math. Bohem. 135 (2010), 239–255.
• [10] P.J. Slater, Leaves of trees, Congr. Numer. 14 (1975), 549–559.
• [11] L. Susilowati, I. Sa'adah, R. Z. Fauziyyah, A. Erfanian, and Slamin, The dominant metric dimension of graphs, Heliyon 6 (2020), e03633.
• [12] M. Tavakoli and S. Klavzar, Distribution of global defensive ˇ k-alliances over some graph products, Cent. Eur. J. Oper. Res. 27 (2019), 615–623.
• [13] M. Tavakoli, F. Rahbarnia, and A.R. Ashrafi, Studying the corona product of graphs under some graph invariants, Trans. Comb. 3 (2014), 43–49.
• [14] E. Zhu, A. Taranenko, Z. Shao, and J. Xu, On graphs with the maximum edge metric dimension, Discrete Appl. Math. 257 (2019), 317–324.