# Eva Zmazek: Strong edge geodetic problem

Date: 24. 5. 2020

Source: Discrete mathematics seminar

Source: Discrete mathematics seminar

Torek, 26. 5. 2020, od 10h do 12h, na daljavo

Povezava do seminarja/link to the seminar:

https://zoom.us/j/97972695933?pwd=WENXSWQvbjhXdW9uYkl0TzlCZmpxQT09

A subset *S* of vertices *V*(*G*) for a graph *G* is a strong edge geodetic
set if we can assign one shortest path to each pair of vertices in *S *
such that the union of edges from these paths is exactly the edge set *
E*(*G*). The strong edge geodetic problem is to find
strong edge geodetic set of minimal cardinality.

In the seminar, we will show that a strong edge geodetic problem is NP-complete. We will also determine strong geodetic number for selected families of graphs and prove some general bounds.