The strong edge geodetic problem is finding the smallest subset $U$ of vertices in a graph $G$ such that for every pair of vertices in $U$, one can assign a shortest path between them in a way that the union of all such paths covers every edge of $G$. As the problem is known to be NP-hard, this dissertation focuses on solving it within specific families of graphs. We show that all simplicial vertices belong to every strong edge geodetic problem, which yields complete solutions for trees, stars, complete graphs, and several others. Furthermore, any vertex with a dominating neighbor must also be included in every such set. Using this property, we characterize graphs for which the only strong geodetic connection set is the entire vertex set and graphs for which the smallest such set has size $n(G) − 1$. A significant part of the dissertation investigates the problem on Cartesian products of graphs. We provide exact solutions for $P_n \square P_m$ when $m = 2, 3$, or $4$, along with two general upper bounds for arbitrary values of $m$. In the case of strong graph products, we present complete solutions. We also analyze complete multipartite graphs and derive exact values for their strong edge geodetic number. Finally, we study Sierpiński graphs, where the problem is closely related to geodetic, strong geodetic, and edge geodetic problem. For these graphs, we provide an upper bound on the size of the smallest strong geodetic connection set and conjecture that this bound is tight.
|
