Proof. MGS is obviously in NP. We define a directed acyclic geodetic graph \(G_{X,\mathcal{C}}\) for an X3C instance \(X=\{x_1,\ldots,x_{3n}\}\) and \(\mathcal{C}=\{C_1,\ldots,C_m\}\) such that \(G_{X,\mathcal{C}}\) has a geodetic set with at most \(7n+m\) vertices if and only if \(X,\mathcal{C}\) has a solution for X3C. The vertices and edges of \(G_{X,\mathcal{C}}\) are defined as follows (see figure 2 for an example). \[V(G_{X,\mathcal{C}}) = \{u_1,\ldots,u_m,\,\widetilde{C}_1,\ldots,\widetilde{C}_{m},\,\widetilde{x}_1,\ldots,\widetilde{x}_{3n}\,v_1,\ldots,v_{3n},\,y_1,\ldots,y_{3n},\,w_1,\ldots,w_{3n}\} \\None\] and \[\begin{array}{lll} E(G_{X,\mathcal{C}}) = & & \{(u_j,\widetilde{C}_j)~|~1 \leq j \leq m\} \\ & \cup & \{(u_j,w_i)~|~1 \leq j \leq m, \, 1 \leq i \leq 3n\} \\ & \cup & \{(\widetilde{C}_j,\widetilde{x}_i)~|~1 \leq j \leq m, \, x_i \in C_j\} \\ & \cup & \{(\widetilde{x}_i,v_i)~|~1 \leq i \leq 3n\} \\ & \cup & \{(\widetilde{x}_i,y_i)~|~1 \leq i \leq 3n\} \\ & \cup & \{(y_i,w_i)~|~1 \leq i \leq 3n\} \\ \end{array}\] Graph \(G_{X,\mathcal{C}}\) has a vertex \(\widetilde{x_i}\) for every \(x_i \in X\) and a vertex \(\widetilde{C_j}\) for every \(C_j \in \mathcal{C}\). The vertices \(v_1,\ldots,v_{3n}\) are necessary to ensure that all vertices \(\widetilde{x}_i\) and \(\widetilde{C}_{j}\) are covered. While these vertices could alternatively connected directly to the \(\widetilde{C_j}\) vertices, but doing so would make the proof harder to follow. It has \(6n+m\) terminal vertices \(u_1,\ldots,u_j,\,v_1,\ldots,v_{3n},\,w_1,\ldots,w_{3n}\) and can be constructed in polynomial time from instance \(X,\mathcal{C}\). It is easy to check that \(G_{X,\mathcal{C}}\) is geodetic.

The only vertices of \(G_{X,\mathcal{C}}\) that are not already covered by shortest paths from terminal start vertices to terminal end vertices are the vertices \(y_1,\ldots,y_{3n}\). It remains to show that \(G_{X,\mathcal{C}}\) has a geodetic set with at most \(7n+m\) vertices if and only if \(X,\mathcal{C}\) has a solution for X3C.

\(\Rightarrow\) Suppose there is a subset \(\mathcal{C'} \subseteq \mathcal{C}\) with \(n\) three-element sets such that every element of \(X\) occurs in exactly one member of \(\mathcal{C'}\), then vertex set \(S=R(G_{X,\mathcal{C}}) \cup \{ \widetilde{C}_{j} ~|~ C_j \in \mathcal{C'}\}\) is a geodetic set with \((6n+m)+n = 7n+m\) vertices.

\(\Leftarrow\) Conversely, let \(S\) be a geodetic set of \(G_{X,\mathcal{C}}\) with at most \(7n+m\) vertices. Since \(G_{X,\mathcal{C}}\) has exactly \(6n+m\) terminal vertices, the set \(S\) has at most \(n\) non-terminal vertices. In order to cover the \(3n\) vertices \(y_1,\ldots,y_{3n}\) with shortest paths, at least \(n\) of the \(m\) non-terminal vertices \(\widetilde{C}_j\), \(1 \leq j \leq m\), are necessary. Thus, \(S\) has exactly \(n\) vertices \(\widetilde{C}_j\) and the set \(\{C_j ~|~ \widetilde{C}_j \in S\}\) is a solution for X3C for instance \(X,\mathcal{C}\). ◻

Proof. The proof is similar to the proof of theorem 1. MEGS is obviously in NP. We again define a directed acyclic geodetic graph \(G_{X,\mathcal{C}}\) for an X3C instance \(X=\{x_1,\ldots,x_{3n}\}\) and \(\mathcal{C}=\{C_1,\ldots,C_m\}\) such that \(G_{X,\mathcal{C}}\) has an edge geodetic set with at most \(7n+m\) vertices if and only if \(X,\mathcal{C}\) has a solution for X3C. The vertices and edges of \(G_{X,\mathcal{C}}\) are defined as in theorem 1. The only difference is the omission of the vertices \(y_1,\ldots,v_{3n}\). These vertices are bridged with edges from the vertices \(\widetilde{x}_i\) to the vertices \(w_i\), see figure 3 for an example. \[V(G_{X,\mathcal{C}}) = \{u_1,\ldots,u_m,\,\widetilde{C}_1,\ldots,\widetilde{C}_{m},\,\widetilde{x}_1,\ldots,\widetilde{x}_{3n}\,v_1,\ldots,v_{3n},\,w_1,\ldots,w_{3n}\} \\None\] and \[\begin{array}{lll} E(G_{X,\mathcal{C}}) = & & \{(u_j,\widetilde{C}_j)~|~1 \leq j \leq m\} \\ & \cup & \{(u_j,w_i)~|~1 \leq j \leq m, \, 1 \leq i \leq 3n\} \\ & \cup & \{(\widetilde{C}_j,\widetilde{x}_i)~|~1 \leq j \leq m, \, x_i \in C_j\} \\ & \cup & \{(\widetilde{x}_i,v_i)~|~1 \leq i \leq 3n\} \\ & \cup & \{(\widetilde{x}_i,w_i)~|~1 \leq i \leq 3n\} \\ \end{array}\] It is easy to see that this graph \(G_{X,\mathcal{C}}\) is also geodetic.

The only edges of \(G_{X,\mathcal{C}}\) that are not already covered by shortest paths from terminal start vertices to terminal end vertices are the edges \((\widetilde{x}_1,w_1),\ldots,(\widetilde{x}_{3n},w_{3n})\). The argument that \(G_{X,\mathcal{C}}\) has an edge geodetic set with at most \(7n+m\) vertices if and only if \(X,\mathcal{C}\) has a solution for X3C is the same as in the proof of theorem 1.

\(\Rightarrow\) Suppose there is a subset \(\mathcal{C'} \subseteq \mathcal{C}\) with \(n\) three-element sets such that every element of \(X\) occurs in exactly one member of \(\mathcal{C'}\), then vertex set \(S=R(G_{X,\mathcal{C}}) \cup \{ \widetilde{C}_{j,j} ~|~ C_j \in \mathcal{C'}\}\) is an edge geodetic set set with \(7n+m\) vertices.

\(\Leftarrow\) Conversely, let \(S\) be an edge geodetic set of \(G_{X,\mathcal{C}}\) with at most \(7n+m\) vertices. Since \(G_{X,\mathcal{C}}\) has exactly \(6n+m\) terminal vertices, the set \(S\) has at most \(n\) non-terminal vertices. In order to cover the \(3n\) edges \((\widetilde{x}_1,w_1),\ldots,(\widetilde{x}_{3n},w_{3n})\) with shortest paths, at least \(n\) of the \(m\) non-terminal vertices \(\widetilde{C}_j\), \(1 \leq j \leq m\), are necessary. Thus, \(S\) has exactly \(n\) vertices \(\widetilde{C}_j\) and the set \(\{C_j ~|~ \widetilde{C}_j \in S\}\) is a solution for X3C for instance \(X,\mathcal{C}\). ◻

Proof. MGS in NP because for a given set of vertices \(S\) it is easy to check that \(S\) is a geodetic set.

We now show how to create, in polynomial time, a directed acyclic planar geodetic graph \(G_{X,\mathcal{C}}\) for a given Planar 3-Sat instance \(X,\mathcal{C}\) with \(m\) clauses. The Graph \(G_{X,\mathcal{C}}\) has a geodetic set containing at most \(29 m\) vertices if and only if there is a truth assignment \(f:X \to \{\text{true},\text{false}\}\) that satisfies every clause \(C_j \in \mathcal{C}\).

The procedure is as follows. We design a gadget graph \(G^{X}_{r}\) for the variables and a gadget graph \(G^{\mathcal{C}}\) for the clauses. Let \(r_i\) be the total number of literals for variable \(x_i\) in all clauses \(C_1,\ldots,C_m\). Then in graph \(G_{X,\mathcal{C}}\) there is a copy \(G_{x_i}\) of gadget \(G^{X}_{r_i}\) for each variable \(x_i \in X\) and a copy \(G_{C_j}\) of gadget \(G^{\mathcal{C}}\) for each clause \(C_j \in \mathcal{C}\). Copy \(G_{x_i}\) is connected to copy \(G_{C_j}\) via directed edges from vertices of \(G_{x_i}\) to vertices of \(G_{C_j}\) if and only if clause \(C_j\) contains a literal for variable \(x_i\). The final resulting graph \(G_{X,\mathcal{C}}\) will be acyclic planar and geodetic and has a geodetic set with at most \(29 m\) vertices if and only if there is a truth assignment \(f:X \to \{\text{true},\text{false}\}\) for \(X\) that satisfies every clause \(C_j \in \mathcal{C}\).

• The definition of variable gadget \(G^{X}_{r}\):

  Let \(J\) be the graph with vertex set \(V(J)=\{T,F,O,I_1,\ldots,I_6,u_1,\ldots,u_7\}\) and edge set \[E(J)=\left\{ \begin{array}{l} (O,T),(O,F),(O,u_4),(O,u_7), (T,I_1),\\ (u_1,T),(u_1,I_2),\\ (u_2,F),(u_2,I_3),\\ (u_3,I_1),\\ (u_4,u_1),(u_4,u_3),(u_4,u_5),(u_4,I_5),\\ (u_5,I_5),(u_5,I_6),\\ (u_6,u_5),(u_6,I_4),\\(u_7,u_2),(u_7,u_6),(u_7,I_6) \end{array}\right\},\] see also figure 5.

  

  Variable gadget \(G^{X}_{r}\) is composed from \(r\) copies \(J_1,\ldots,J_r\) of graph \(J\) in a circular manner as shown in figure 6. Let \[T^{(k)},F^{(k)},O^{(k)},I_1^{(k)},\ldots,I_6^{(k)},u_1^{(k)},\ldots,u_7^{(k)}\] be the vertices \[T,F,O,I_1,\ldots,I_6,u_1,\ldots,u_7\] of the \(k\)-th copy \(J_k\), \(1 \leq k \leq r\), in \(G^{X}_{r}\) and let \[\begin{array}{lll} T^{(\star)} & = & \{T^{(k)}~|~1 \leq k \leq r\}, \\ F^{(\star)} & = & \{F^{(k)}~|~1 \leq k \leq r\}, \\ O^{(\star)} & = & \{O^{(k)}~|~1 \leq k \leq r\}, \\ u_3^{(\star)} & = & \{u_3^{(k)}~|~1 \leq k \leq r\}, \\ u_4^{(\star)} & = & \{u_4^{(k)}~|~1 \leq k \leq r\}, \\ u_5^{(\star)} & = & \{u_5^{(k)}~|~1 \leq k \leq r\}, \\ u_7^{(\star)} & = & \{u_7^{(k)}~|~1 \leq k \leq r\} \end{array}\] The \(r\) copies of \(J\) are connected by additional edges. These are the edges from \(F^{(k)}\) to \(I^{(k')}_1\) and the edges from \(u^{(k)}_7\) to \(u^{(k')}_3\) where \(k' = (k \bmod r)+1\).

  

  The dashed lines in figure 6 show the vertices and edges of the neighboring copies of \(J\) in gadget \(G^{X}_{r}\) and the possible outgoing edges to a copy of a clause gadget \(G^{\mathcal{C}}\) in \(G_{X,\mathcal{C}}\). The dashed lines in figure 6 shows the possible outgoing edges from vertices of a copy of \(G^{X}_{r}\) to vertices of a copy of a clause gadget. Only the vertices of \(O^{(\star)} \cup T^{(\star)} \cup F^{(\star)}\) will get additional outgoing edges in \(G_{X,\mathcal{C}}\).

  Graph \(J\) has one terminal start vertex \(O\) and 6 terminal end vertices \(I_1,\ldots,I_6\). Thus variable gadget \(G^{X}_{r}\) has \(r\) terminal start vertices and \(6 r\) terminal end vertices. The terminal start vertices of the copies of \(G^{X}_{r}\) will also be terminal start vertices in \(G_{X,\mathcal{C}}\), because there will be no additional edges in \(G_{X,\mathcal{C}}\) to the vertices of these copies. The terminal end vertices of the copies of \(G^{X}_{r}\) will also be terminal end vertices in \(G_{X,\mathcal{C}}\), because there will be no additional edges in \(G_{X,\mathcal{C}}\) from these vertices of these copies.

  It is easy to check that the shortest paths from the terminal start vertices to the terminal end vertices of \(G^{X}_{r}\) cover all vertices of \(G^{X}_{r}\) except the \(2 r\) vertices of \(u_3^{(\star)} \cup u_5^{(\star)}\). These vertices are colored gray in figure 6.

  It is also easy to check that variable gadget \(G^{X}_{r}\) is acyclic, planar and geodetic, and has exactly two minimum geodetic sets \(R(G^{X}_{r}) \cup u_4^{(\star)}\) and \(R(G^{X}_{r}) \cup u_7^{(\star)}\) with \(8 r\) vertices. The first set is called a minimum geodetic set of type true and the second set is called a minimum geodetic set of type false.

  Another interesting property of the variable gadget \(G^{X}_{r}\) is the following. For each \(k\), \(1 \leq k \leq r\), there is

  1. a path from vertex \(u_4^{(k)}\) to vertex of \(T^{(k)}\) and no path from \(u_4^{(k)}\) to a vertex of \((T^{(\star)} \cup F^{(\star)}) \setminus \{T^{(k)}\}\) and

  2. a path from vertex \(u_7^{(k)}\) to vertex \(F^{(k)}\) and no path from \(u_7^{(k)}\) to a vertex of \((T^{(\star)} \cup F^{(\star)}) \setminus \{F^{(k)}\}\).

  The vertex triples \((T^{(k)},O^{(k)},F^{(k)})\), \(1 \leq k \leq r\), are called the variable ports of \(G^{X}_{r}\). For each \(k\), \(1 \leq k \leq r\), either the two vertices \(T^{(k)},O^{(k)}\) or the two vertices \(O^{(k)},F^{(k)}\) will be connected in \(G_{X,\mathcal{C}}\) via directed edges to vertices from a clause gadget \(G^{\mathcal{C}}\).

• The definition of clause gadget \(G^{\mathcal{C}}\):

  The clause gadget \(G^{\mathcal{C}}\) has vertex set \[V(G^{\mathcal{C}})=\{\hat{I}_1,\,\hat{I}_2,\,\hat{I}_3,\,\hat{I}_4,\,\hat{I}_5,\,v_{1,1},\,v_{2,1},\,v_{2,2},\,v_{3,1},\,v_{3,2},\,v_{3,3},\,w\}\] and edge set

  \[E(G^{\mathcal{C}}) = \left\{ \begin{array}{l} (v_{1,1},\hat{I}_3),(v_{1,1},\hat{I}_1),(v_{2,1},\hat{I}_1), (v_{2,1},\hat{I}_2),(v_{3,1},\hat{I}_2),(v_{3,1},\hat{I}_3),\\ (v_{1,1},w),\\ (v_{2,1},v_{2,2}),(v_{2,2},w),(v_{2,2},\hat{I}_5),\\ (v_{3,1},v_{3,2}),(v_{3,2},v_{3,3}),(v_{3,3},w),(v_{3,3},\hat{I}_4), \\ (w,\hat{I}_1),(w,\hat{I}_2),(w,\hat{I}_3) \end{array} \right\},\] see figure 7. The vertices \(\hat{I}_1, \ldots, \hat{I}_5\) are terminal end vertices in the clause gadget and also in the final graph \(G_{X,\mathcal{C}}\), because there are no outgoing edges from vertices of a copy of a clause gadget in \(G_{X,\mathcal{C}}\). The dashed lines in figure 7 indicate all possible incoming edges from vertices of a copy of a variable gadget in \(G_{X,\mathcal{C}}\).

  

  The planar embedding given in figure 7 defines in a circle around to the left along the outer face three vertex triples \((v_{1,1},\hat{I}_1,v_{2,1})\), \((v_{2,1},\hat{I}_2,v_{3,1})\) and \((v_{3,1},\hat{I}_3,v_{1,1})\). These vertex triples are called clause ports.

• The definition of graph \(G_{X,\mathcal{C}}\):

  The final graph \(G_{X,\mathcal{C}}\) has for each variable \(x_i \in X\) a copy \(G_{x_i}\) of variable gadget \(G^{X}_{r_i}\) and for each clause \(C_j \in \mathcal{C}\) a copy \(G_{C_j}\) of clause gadget \(G^{\mathcal{C}}\).

  Figure 8 shows the connections between the variable graphs \(G_{x_i}\) and the clause graphs \(G_{C_j}\).

  If clause \(C_j\) contains a literal for variable \(x_i\) then 4 edges are inserted from the vertices of a clause port \((T^{(k)},O^{(k)},F^{(k)})\) of \(G_{x_i}\) to the vertices of a variable port \((v_{l,1},\hat{I}_l,v_{l'.1})\) of \(G_{C_j}\). When choosing the variable port and clause port, the planar embedding of the variable clause graph of the Planar-3-Sat instance \(X,\mathcal{C}\) must be taken into account.

  If literal \(x_i \in C_j\) then the 4 edges \[(T^{(k)},v_{l,1}),~(O^{(k)},v_{l,1}),~(O^{(k)},\hat{I}_{l,1}),~(O^{(k)},v_{l',1})\] are inserted, if literal \(\overline{x_i} \in C_j\) then the 4 edges \[(O^{(k)},v_{l,1}),~(O^{(k)},\hat{I}_{l,1}),~(O^{(k)},v_{l',1}),~(F^{(k)},v_{l',1})\] are inserted.

  

  • The top row of figure 8 (tiles 1, 2 and 3) shows the case in which literal \(x_i\) is in \(C_j\). In this case there is an edge from vertex \(T^{(k)}\) to vertex \(v_{l,1}\) of \(G_{C_j}\).

  • The bottom row of figure 8 (tiles 4, 5 and 6) shows the case in which literal \(\overline{x_i}\) is in \(C_j\).In this case there is an edge from vertex \(F^{(k)}\) to vertex \(v_{l',1}\).

  • In the first column of figure 8 (tiles 1 and 4) the vertices not covered by \(R(G_{X,\mathcal{C}})\) are colored gray.

  • In the second column of figure 8 (tiles 2 and 5), the vertices not covered by a minimum geodetic set of type true for \(G_{x_i}\) are colored gray.

  • In the third column of figure 8 (tiles 3 and 6), the vertices not covered by a minimum geodetic set of type false for \(G_{x_i}\) are colored gray.

  In the first case where literal \(x_i \in C_j\), vertex \(w\) from \(G_{C_j}\) is covered by the geodetic set of type true. This is because there is a shortest path from \(u_4^{(k)}\) via \(u_1^{(k)}\) to \(T^{(k)}\) in the copy of \(J\), see figure 5, and then either via the vertices \(v_{1,1}\) and \(w\) to vertex \(\hat{I}_{2}\), or via the vertices \(v_{2,1}\), \(v_{2,2}\) and \(w\) to vertex \(\hat{I}_{3}\) or via the vertices \(v_{3,1}\), \(v_{3,2}\), \(v_{3,3}\) and \(w\) to vertex \(\hat{I}_{1}\), respectively, see figure 8. Which cases actually occur depends on which clause port is connected to which variable port.

  In the second case where literal \(\overline{x_i} \in C_j\), vertex \(w\) from \(G_{C_j}\) is covered by the geodetic set of type false. This is because there is a shortest path from \(u_7^{(k)}\) via \(u_2^{(k)}\) to \(F^{(k)}\) in the copy of \(J\), see figure 5, and then either via the vertices \(v_{1,1}\) and \(w\) to vertex \(\hat{I}_{2}\), or via the vertices \(v_{2,1}\), \(v_{2,2}\) and \(w\) to vertex \(\hat{I}_{3}\) or via the vertices \(v_{3,1}\), \(v_{3,2}\), \(v_{3,3}\) and \(w\) to vertex \(\hat{I}_{1}\), respectively, see figure 8.

  Graph \(G_{X,\mathcal{C}}\) is acyclic, planar and geodetic.

It remains to show that if there is a truth assignment \(f:X \to \{\text{true},\text{false}\}\) that satisfies every clause \(C_j \in \mathcal{C}\) then \(G_{X,\mathcal{C}}\) has a geodetic set with at most \(29 m\) vertices and if \(G_{X,\mathcal{C}}\) has a geodetic set with at most \(29 m\) vertices then there is a truth assignment \(f:X \to \{\text{true},\text{false}\}\) that satisfies every clause \(C_j \in \mathcal{C}\).

\(\Rightarrow\) Suppose \(f:X \to \{\text{true},\text{false}\}\) is a truth assignment for \(X\) that satisfies every clause \(C_j \in \mathcal{C}\). Let \(S_{x_i}\) be a minimum geodetic set of copy \(G_{x_i}\) of type true if \(f(x_i) = \text{true}\), or of type false if \(f(x_i) = \text{false}\). Then the union of all \(S_{x_i}\), \(x_i \in X\), and the the set of all terminal vertices of all \(G_{C_j}\) is a geodetic set with \(29 m\) vertices.

\(\Leftarrow\) Suppose \(S\) is a geodetic set of \(G_{X,\mathcal{C}}\) with at most \(29 m\) vertices. Let \[u_{3}^{(k,i)},u_{4}^{(k,i)},u_{5}^{(k,i)},u_{7}^{(k,i)},\] \(1 \leq k \leq r_i\), be the vertices \[u_{3}^{(k)},u_{4}^{(k)},u_{5}^{(k)},u_{7}^{(k)}\] of gadget \(G^{X}_{r_i}\) in graph \(G_{x_i}\) of \(G_{X,\mathcal{C}}\), and let \(w^{(j)}\), \(1 \leq j \leq m\), be the vertex \(w\) of gadget \(G^{\mathcal{C}}\) in graph \(G_{C_j}\) of \(G_{X,\mathcal{C}}\). Vertex set \(S\) must contain the \(7 \cdot 3 m = 21 m\) terminal vertices of all \(G_{x_i}\), \(x_i \in X\), and the \(5 \cdot m\) terminal vertices of all \(G_{C_j}\), \(C_j \in \mathcal{C}\). In addition, \(S\) must contain \(1 \cdot 3 m\) vertices from the set \[\{u_{4}^{(k,i)},u_{7}^{(k,i)}~|~1 \leq k \leq r_i, 1 \leq i \leq n\}\] to cover all vertices \(u_{3}^{(k,i)}\) and \(u_{5}^{(k,i)}\) for \(1 \leq k \leq r_i\) and \(1 \leq i \leq n\). More precisely, \(S\) must contain for each \(x_i \in X\) all vertices \(u_{4}^{(k,i)}\) or all vertices \(u_{7}^{(k,i)}\), \(1 \leq k \leq r_i\). Since \(S\) covers all \(m\) vertices \(w^{(j)}\) of \(G_{C_j}\), \(C_j \in \mathcal{C}\), the truth assignment \(f:X \to \{\text{true},\text{false}\}\) defined by \[f(x_i) = \left\{ \begin{array}{ll} \text{true} & \text{if } S \cap V(G_{x_i}) \text{ is a minimum geodetic set of } G_{x_i} \text{ of type true}\\ \text{false} & \text{if } S \cap V(G_{x_i}) \text{is a minimum geodetic set of } G_{x_i} \text{ of type false} \end{array} \right.\] satisfies every clause \(C_j \in \mathcal{C}\).

The transformation can obviously be done in polynomial time. ◻

Proof. We first consider the case for geodetic sets. After that we consider the case for edge geodetic sets.

We prove the theorem by contradiction. For two vertices \(x,y\) contained in a geodetic set, any third vertex \(w\) is never exclusively covered by the shortest path between \(x\) and \(y\). If a vertex \(w \in V \setminus S\) lies not on a shortest path from vertex \(s\) to a vertex \(y \in S\) and not on a shortest path from a vertex \(x \in S\) to \(t\), then a subdivision of the diamond digraph \(\vec{D}\) from figure 10 is a subgraph of \(G\), which contradicts the property that series-parallel graphs do not contain a subdivision of \(\vec{D}\) as a subgraph.

Let \(x\not=s\), \(y\not=t\) and \(P_{s \mapsto x \mapsto w \mapsto y \mapsto t}\) be a path in \(G\) from vertex \(s\) via vertex \(x\) via vertex \(w\) via vertex \(y\) to vertex \(t\), where the subpath \(P_{x \mapsto w \mapsto y}\) of \(P_{s \mapsto x \mapsto w \mapsto y \mapsto t}\) from \(x\) via \(w\) to \(y\) is a shortest path. See Graph a) in figure 11. Every path in \(G\) is simple. A path cannot contain a vertex more than once, since \(G\) is cycle-free.

Next let \(P_{s \mapsto y}\) be a shortest path from \(s\) to \(y\) and \(P_{x \mapsto t}\) be a shortest paths from \(x\) to \(t\). See Graph b) in figure 11. Path \(P_{s \mapsto y}\) does not contain any vertex of path \(P_{x \mapsto w}\), since otherwise there exists a shortest path from \(s\) to \(y\) containing vertex \(w\), which contradicts our assumptions. For the same reason, path \(P_{x \mapsto t}\) does not contain any vertex of path \(P_{w \mapsto y}\).

Therefore, let \(s'\) be the last vertex of \(P_{s \mapsto y}\) that is also in \(P_{s \mapsto x}\) and \(y'\) be the first vertex of \(P_{s \mapsto y}\) that is also in \(P_{w \mapsto y}\). Let \(x'\) be the last vertex of \(P_{x \mapsto t}\) that is also in \(P_{x \mapsto w}\) and \(y'\) be the first vertex of \(P_{x \mapsto t}\) that is also in \(P_{y \mapsto t}\). See Graph c) in figure 11.

If the two subpaths \(P_{s' \mapsto y'}\) and \(P_{x' \mapsto t'}\) of \(P_{s \mapsto y}\) and \(P_{x \mapsto t}\), respectively, are vertex disjoint, then \(G\) has a subdivision of diamond digraph \(\vec{D}\) of figure 10, where \(a=s'\), \(b=x'\), \(c=y'\) and \(d=t'\). See Graph c) in figure 11. Suppose \(P_{s' \mapsto y'}\) and \(P_{x' \mapsto t'}\) have a common vertex. Then let \(z\) be the first common vertex of these two path. In this case, \(G\) also contains a subdivision of the diamond digraph \(\vec{D}\), where \(a=s'\), \(b=x'\), \(c=z\), and \(d=y'\). See Graph d) in figure 11.

The proof for edge geodetic sets is analogous. Let \((w,w')\) be an edge on a shortest path from \(x\) to \(y\). Then we consider the path \(P_{s \mapsto x \mapsto w, w' \mapsto y \mapsto t}\) with the subpaths \(P_{x \mapsto w}\) and \(P_{w' \mapsto y}\). Path \(P_{s \mapsto y}\) does not contain any vertex of path \(P_{x \mapsto w}\) and path \(P_{x \mapsto t}\) does not contain any vertex of path \(P_{w' \mapsto y}\). Therefore, let \(s'\) be the last vertex of \(P_{s \mapsto y}\) that is also in \(P_{s \mapsto x}\) and \(y'\) be the first vertex of \(P_{s \mapsto y}\) that is also in \(P_{w' \mapsto y}\). Let \(x'\) be the last vertex of \(P_{x \mapsto t}\) that is also in \(P_{x \mapsto w}\) and \(y'\) be the first vertex of \(P_{x \mapsto t}\) that is also in \(P_{y \mapsto t}\). The further argumentation is the same as for geodetic sets. ◻

Proof. The first case is obvious. Since the initial series-parallel digraph \(I_{(s,t)}\) is explicitly defined, the values can be easily verified. The calculations of the number of edges on a shortest path from \(s\) to \(t\) in all three sub-cases 1.(a), 2.(a) and 3.(a) are also obvious. Therefore, we only consider the cases 2.(b), 2.(c), 3.(b) and 3.(c) in more detail.

2. (series composition)

   Every geodetic set \(T\) of \(G \updownarrow G'\) has at least \(\text{mgs}(G) + \text{mgs}(G') -2\) vertices, because \(S=(T \cap V(G)) \cup \{t\}\) is a geodetic set of \(G\) and \(S'=(T \cap V(G')) \cup \{s'\}\) is a geodetic set of \(G'\). This implies that \(|T| \geq |S|+|S'|-2 \geq \text{mgs}(G) + \text{mgs}(G') -2\).

   2. Let \(S\) be a minimum geodetic set of \(G\), \(S'\) be a minimum geodetic set of \(G'\) and \(T^{\text{\,-} t,\text{\,-} s'} = (S \setminus \{t\}) \cup (S' \setminus \{s'\})\).

      Vertex set \(T^{\text{\,-} t,\text{\,-} s'}\) is a geodetic set of \(G \updownarrow G'\) with \(\text{mgs}(G)+\text{mgs}(G')-2\) vertices because in \(G \updownarrow G'\)

      1. every vertex \(u \in V(G) \setminus T^{\text{\,-} t,\text{\,-} s'}\), \(u \not = t\), is on a shortest path from a vertex of \(S \setminus \{t\}\) to a vertex of \((S \setminus \{t\}) \cup \{t'\}\),

      2. every vertex \(u \in V(G') \setminus T^{\text{\,-} t,\text{\,-} s'}\), \(u \not = s'\), is on a shortest path from a vertex of \((S' \setminus \{s'\}) \cup \{s\}\) to a vertex of \(S' \setminus \{s'\}\) and

      3. vertex \(t\) is on a shortest path from vertex \(s\) to vertex \(t'\).

   3. Let \(S\) be a minimum geodetic set of \(G\), \(S'\) be a minimum geodetic set of \(G'\) and \(T^{\text{\,-} s'} = S \cup (S' \setminus \{s'\})\).

      Vertex set \(T^{\text{\,-} s'}\) is a closed geodetic set of \(G \updownarrow G'\) with \(\text{mgs}(G)+\text{mgs}(G')-1\) because every vertex of \(V(G \updownarrow G') \setminus T^{\text{\,-} s'}\) is on a shortest path in \(G \updownarrow G'\) from a vertex of \(S\) to a vertex of \(S\) or from a vertex of \((S' \setminus \{s'\}) \cup \{t\}\) to a vertex of \((S' \setminus \{s'\}) \cup \{t\}\).

      Sometimes, however, vertex set \(T^{\text{\,-} t,\text{\,-} s'}\) as defined in case (b) is already a closed geodetic set of \(G \updownarrow G'\) with \(\text{mgs}(G)+\text{mgs}(G')-2\) vertices. This is the case if \(S\) and \(S'\) contain more vertices than one source vertex and one target vertex, i.e., \(|S| > 2\) and \(|S'| > 2\). It is also the case if \(S\) or \(S'\) contain more vertices than one source vertex and one target vertex and is itself a closed geodetic set. This is the case if and only if \(\text{mgs}(G) = \text{cmgs}(G) > 2\) or \(\text{mgs}(G') = \text{cmgs}(G') > 2\), respectively.

3. (parallel composition)

   Every geodetic set \(T\) of \(G \leftrightarrow G'\) has at least \(\text{mgs}(G) + \text{mgs}(G') -2\) vertices because \(S=T \cap V(G)\) is a geodetic set of \(G\), \(S'=(T \cap V(G')) \cup \{s',t'\}\) is a geodetic set of \(G'\) and \(|T| = |S|+|S'|-2 \geq \text{mgs}(G) + \text{mgs}(G') -2\). Here \(|T| = |S|+|S'|-2\) because \(s'\) and \(t'\) are not vertices of \(G \leftrightarrow G'\) and thus not vertices of \(T\).

   2. 1. Let \(\text{sp}(G) = \text{sp}(G')\), \(S\) be a minimum geodetic set of \(G\), \(S'\) be a minimum geodetic set of \(G'\) and \(T^{\text{\,-} s',\text{\,-} t'} = S \cup (S' \setminus \{t',s'\})\).

         Vertex set \(T^{\text{\,-} s',\text{\,-} t'}\) is a geodetic set of \(G \leftrightarrow G'\) with \(\text{mgs}(G)+\text{mgs}(G')-2\) vertices because every vertex \(u \in V(G \leftrightarrow G') \setminus T^{\text{\,-} s',\text{\,-} t'}\) is on a shortest path from a vertex of \(S\) to a vertex of \(S\) if \(u \in V(G)\), or from a vertex of \((S' \setminus \{s',t'\}) \cup \{s,t\}\) to a vertex of \((S' \setminus \{s',t'\}) \cup \{s,t\}\) if \(u \in V(G')\).

      2. Let \(\text{sp}(G) < \text{sp}(G')\), \(S\) be a minimum geodetic set of \(G\), \(S'_c\) be a minimum closed geodetic set of \(G'\) and \(T_c^{\text{\,-} s',\text{\,-}t'} = S \cup (S'_c \setminus \{s',t'\})\). Every minimum geodetic set for \(G \leftrightarrow G'\) has at least \(|S|+|S'|-2 = \text{mgs}(G) + \text{cmgs}(G') -2\) vertices, since the pair \(s,t\) cannot cover any vertices of \(G'\).

         Vertex set \(T_c^{\text{\,-} s',\text{\,-}t'}\) is a geodetic set of \(G \leftrightarrow G'\) with \(\text{mgs}(G)+\text{cmgs}(G')-2\) vertices because every vertex \(u \in V(G \leftrightarrow G') \setminus T_c^{\text{\,-} s',\text{\,-}t'}\) is on a shortest path

         1. from a vertex of \(S\) to a vertex of \(S\), if \(u \in V(G)\) or

         2. from a vertex of \((S'_c \setminus \{s',t'\}) \cup \{s\}\) to a vertex of \(S'_c \setminus \{s',t'\}\) or from a vertex of \(S'_c \setminus \{s',t'\}\) to a vertex of \((S'_c \setminus \{s',t'\}) \cup \{t\}\), if \(u \in V(G')\).

         Vertex set \(T_c^{\text{\,-} s',\text{\,-}t'}\) is a minimum geodetic set of \(G \leftrightarrow G'\) because \(R = T_c^{\text{\,-} s',\text{\,-}t'} \cap V(G)\) is a geodetic set of \(G\), \(R'_c = (T_c^{\text{\,-} s',\text{\,-}t'} \cap V(G')) \cup \{s',t'\}\) is a closed geodetic set of \(G'\) and \(|T_c^{\text{\,-} s',\text{\,-}t'}| = |R| + |R'_c| - 2\).

      3. If \(\text{sp}(G) > \text{sp}(G')\) then exchange \(G\) and \(G'\) and consider the case where \(\text{sp}(G) < \text{sp}(G')\).

   3. Let \(S_c\) be a minimum closed geodetic set of \(G\), \(S'_c\) be a minimum closed geodetic set of \(G'\) and \(T_{cc}^{\text{\,-} s',t'} = S_c \cup (S'_c \setminus \{s',t'\})\).

      Vertex set \(T_{cc}^{\text{\,-} s',t'}\) is a closed geodetic set of \(G \leftrightarrow G'\) because every vertex \(u \in V(G \leftrightarrow G') \setminus T_{cc}^{\text{\,-} s',t'}\) is on a shortest path

      1. from a vertex of \(S_c\) to a vertex of \(S_c \setminus \{t\}\) or from a vertex of \(S_c \setminus \{s\}\) to a vertex of \(S_c\) , if \(u \in V(G)\), or

      2. from a vertex of \((S'_c \setminus \{s',t'\}) \cup \{s\}\) to a vertex of \(S'_c \setminus \{s',t'\}\) or from a vertex of \(S'_c \setminus \{s',t'\}\) to a vertex of \((S' \setminus \{s',t'\}) \cup \{t\}\), if \(u \in V(G')\).

      Vertex set \(T_{cc}^{\text{\,-} s',t'}\) is a minimum closed geodetic set of \(G \leftrightarrow G'\) because \(R_c = T_{cc}^{\text{\,-} s',t'} \cap V(G)\) is a minimum closed geodetic set of \(G\), \(R'_c = (T_{cc}^{\text{\,-} s',t'} \cap V(G')) \cup \{s',t'\}\) is a minimum closed geodetic set of \(G'\) and \(|T_{cc}^{\text{\,-} s',t'}| = |R_c| + |R'_c| - 2\).

 ◻

Proof. It is only necessary to examine cases 2.(b), 2.(c), 3.(b) and 3.(c) in more detail. Case 1 is obvious, and cases 2.(a) and 3.(a) correspond to those in theorem 5.

2. (series composition)

   Every edge geodetic set \(T\) of \(G \updownarrow G'\) has at least \(\text{megs}(G) + \text{megs}(G') -2\) vertices, because \(S=(T \cap V(G)) \cup \{t\}\) is an edge geodetic set of \(G\) and \(S'=(T \cap V(G')) \cup \{s'\}\) is an edge geodetic set of \(G'\). This implies that \(|T| \geq |S|+|S'|-2 \geq \text{megs}(G) + \text{megs}(G') -2\).

   2. Let \(S\) be a minimum edge geodetic set of \(G\), \(S'\) be a minimum edge geodetic set of \(G'\) and \(T^{\text{\,-} t,\text{\,-} s'} = (S \setminus \{t\}) \cup (S' \setminus \{s'\})\).

      Vertex set \(T^{\text{\,-} t,\text{\,-} s'}\) is an edge geodetic set of \(G \updownarrow G'\) with \(\text{megs}(G)+\text{megs}(G')-2\) vertices because in \(G \updownarrow G'\)

      1. every edge \(e \in E(G)\) is on a shortest path from a vertex of \(S \setminus \{t\}\) to a vertex of \((S \setminus \{t\}) \cup \{t'\}\) and

      2. every edge \(e \in E(G')\) is on a shortest path from a vertex of \((S' \setminus \{s'\}) \cup \{s\}\) to a vertex of \(S' \setminus \{s'\}\).

   3. Let \(S\) be a minimum edge geodetic set of \(G\), \(S'\) be a minimum edge geodetic set of \(G'\) and \(T^{\text{\,-} s'} = S \cup (S' \setminus \{s'\})\).

      Vertex set \(T^{\text{\,-} s'}\) is a closed edge geodetic set of \(G \updownarrow G'\) with \(\text{megs}(G)+\text{megs}(G')-1\) because every edge of \(E(G \updownarrow G')\) is on a shortest path in \(G \updownarrow G'\) from a vertex of \(S\) to a vertex of \(S\) or from a vertex of \((S' \setminus \{s'\}) \cup \{t\}\) to a vertex of \((S' \setminus \{s'\}) \cup \{t\}\).

      Sometimes, however, vertex set \(T^{\text{\,-} t,\text{\,-} s'}\) as defined in case (b) is already a closed edge geodetic set of \(G \updownarrow G'\) with \(\text{megs}(G)+\text{megs}(G')-2\) vertices. This is the case if \(S\) and \(S'\) contain more vertices than one source vertex and one target vertex, i.e., \(|S| > 2\) and \(|S'| > 2\). It is also the case if \(S\) or \(S'\) contain more vertices than one source vertex and one target vertex and is itself a closed edge geodetic set. This is the case if and only if \(\text{megs}(G) = \text{cmegs}(G) > 2\) or \(\text{megs}(G') = \text{cmegs}(G') > 2\), respectively. Recall that, by definition, graphs with sp(G)= 1 do not have closed edge geodetic sets.

3. (parallel composition)

   Every edge geodetic set \(T\) of \(G \leftrightarrow G'\) has at least \(\text{megs}(G) + \text{megs}(G') -2\) vertices because \(S=T \cap V(G)\) is an edge geodetic set of \(G\), \(S'=(T \cap V(G'))\cup \{s',t'\}\) is an edge geodetic set of \(G'\) and \(|T|=|S|+|S'|-2 \geq \text{megs}(G) + \text{megs}(G') -2\).

   2. 1. Let \(\text{sp}(G) = \text{sp}(G')\), \(S\) be a minimum edge geodetic set of \(G\), \(S'\) be a minimum edge geodetic set of \(G'\) and \(T^{\text{\,-} s',\text{\,-} t'} = S \cup (S' \setminus \{t',s'\})\).

         Vertex set \(T^{\text{\,-} s',\text{\,-} t'}\) is an edge geodetic set of \(G \leftrightarrow G'\) with \(\text{megs}(G)+\text{megs}(G')-2\) vertices because in \(G \updownarrow G'\)

         1. every edge \(e \in E(G)\) is on a shortest path from a vertex of \(S\) to a vertex of \(S\) and

         2. every edge \(e \in E(G')\) is on a shortest Path from a vertex of \((S' \setminus \{s',t'\}) \cup \{s,t\}\) to a vertex of \((S' \setminus \{s',t'\}) \cup \{s,t\}\).

      2. Let \(\text{sp}(G) <\text{sp}(G')\), \(S\) be a minimum edge geodetic set of \(G\), \(S'_c\) be a closed minimum edge geodetic set of \(G'\) and \(T_c^{\text{\,-} s',{\text{\,-} t'}} = S \cup (S'_c \setminus \{t',s'\})\). Now every minimum edge geodetic set for \(G \leftrightarrow G'\) has at least \(|S|+|S'|-2 = \text{mgs}(G) + \text{cmgs}(G') -2\) vertices, since the pair \(s,t\) cannot cover any vertices of \(G'\). Since the shortest path of G’ is always greater than 1, the \(\text{megs}\) is always defined.

         Vertex set \(T_c^{\text{\,-} s',{\text{\,-} t'}}\) is an edge geodetic set of \(G \leftrightarrow G'\) with \(\text{megs}(G)+\text{cmegs}(G')-2\) vertices because every edge \(e \in E(G \leftrightarrow G')\) is on a shortest path

         1. from a vertex of \(S\) to a vertex of \(S\), if \(e \in E(G)\) or

         2. from a vertex of \((S'_c \setminus \{s',t'\}) \cup \{s\}\) to a vertex of \(S'_c \setminus \{s',t'\}\) or from a vertex of \(S'_c \setminus \{s',t'\}\) to a vertex of \((S'_c \setminus \{s',t'\}) \cup \{t\}\), if \(e \in E(G')\).

         Vertex set \(T_c^{\text{\,-} s',{\text{\,-} t'}}\) is a minimum edge geodetic set of \(G \leftrightarrow G'\) because \(R = T_c^{\text{\,-} s',{\text{\,-} t'}} \cap V(G)\) is an edge geodetic set of \(G\), \(R'_c = (T_c^{\text{\,-} s',{\text{\,-} t'}} \cap V(G')) \cup \{s',t'\}\) is a closed edge geodetic set of \(G'\) and \(|T_c^{\text{\,-} s',{\text{\,-} t'}}| = |R| + |R'_c| - 2\).

      3. If \(\text{sp}(G) > \text{sp}(G')\) then exchange \(G\) and \(G'\) and consider the case where \(\text{sp}(G) < \text{sp}(G')\).

   3. Let \(S_c\) be a minimum closed edge geodetic set of \(G\), \(S'_c\) be a minimum closed edge geodetic set of \(G'\) and \(T_{cc}^{\text{\,-} s',t'} = S_c \cup (S'_c \setminus \{s',t'\})\).

      Vertex set \(T_{cc}^{\text{\,-} s',t'}\) is a closed edge geodetic set of \(G \leftrightarrow G'\) because every edge \(e \in E(G \leftrightarrow G')\) is on a shortest path

      1. from a vertex of \(S_c\) to a vertex of \(S_c \setminus \{t\}\) or from a vertex of \(S_c \setminus \{s\}\) to a vertex of \(S_c\) , if \(e \in E(G)\), or

      2. from a vertex of \((S'_c \setminus \{s',t'\}) \cup \{s\}\) to a vertex of \(S'_c \setminus \{s',t'\}\) or from a vertex of \(S'_c \setminus \{s',t'\}\) to a vertex of \((S' \setminus \{s',t'\}) \cup \{t\}\), if \(e \in E(G')\).

      Vertex set \(T_{cc}^{\text{\,-} s',t'}\) is a minimum closed edge geodetic set of \(G \leftrightarrow G'\) because \(R_c = T_{cc}^{\text{\,-} s',t'} \cap V(G)\) is a closed edge geodetic set of \(G\), \(R'_c = (T_{cc}^{\text{\,-} s',t'} \cap V(G')) \cup \{s',t'\}\) is a closed edge geodetic set of \(G'\) and \(|T_{cc}^{\text{\,-} s',t'}| = |R_c| + |R'_c| - 2\).

 ◻