Strong Edge Geodetic Problem on Complete Multipartite Graphs and Some Extremal Graphs for the Problem

A set of vertices X of a graph G is a strong edge geodetic set if, to any pair of vertices from X, we can assign one (or zero) shortest path between them, such that every edge of G is contained in at least one on these paths. The cardinality of a smallest strong edge geodetic set of G is the strong edge geodetic number \(\mathrm{sg_e}(G)\) ${\mathrm{sg}}_{\mathrm{e}}(G)$ of G. In this paper, the strong edge geodetic number of complete multipartite graphs is determined. Graphs G with \(\mathrm{sg_e}(G) = n(G)\) ${\mathrm{sg}}_{\mathrm{e}}(G)=n(G)$ are characterized and \(\mathrm{sg_e}\) ${\mathrm{sg}}_{\mathrm{e}}$ is determined for Cartesian products \(P_n\,\square \, K_m\) $P_n\square K_m$ . The latter result in particular corrects an error from the literature.