Eva Zmazek: Strong edge geodetic problem

Datum objave: 24. 5. 2020
Seminar za diskretno matematiko
Torek, 26. 5. 2020, od 10h do 12h, na daljavo

Povezava do seminarja/link to the seminar:


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.