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 sge(G) of G. In this paper, the strong edge geodetic number of complete multipartite graphs is determined. Graphs G with sge(G) = n(G) are characterized and sge is determined for Cartesian products Pn □ Km. The latter result in particular corrects an error from the literature.