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

Abstract

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{s}{\mathrm{g}}_{\mathrm{e}}(G)$ of $G$. In this paper, the strong edge geodetic number of complete multipartite graphs is determined. Graphs $G$ with $\mathrm{s}{\mathrm{g}}_{\mathrm{e}}(G)=n(G)$ are characterized and $\mathrm{s}{\mathrm{g}}_{\mathrm{e}}$ is determined for Cartesian products $P_n\square K_m$. The latter result in particular corrects an error from the literature.