Eva Zmazek: Strong edge geodetic problem on complete bipartite graphs and some extremal graphs for the problem

Datum objave: 24. 2. 2023
Seminar za diskretno matematiko
Plemljev seminar, Jadranska 19

Abstract. A subset U 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 U such that the union of edges from these paths is exactly the edge set E(G) . The cardinality of a smallest strong edge geodetic set of G is the strong edge geodetic number sg_e(G) of G.

In this talk, we will determine sg_e for complete bipartite graphs. We will also characterize graphs G with sg_e(G) = n(G) and determine sg_e for the Cartesian products of paths and complete graphs on n vertices.