1.
Strong edge geodetic problem on complete multipartite graphs and some extremal graphs for the problemSandi Klavžar,
Eva Zmazek, 2024, original scientific article
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 ${\rm sg_e}(G)$ of $G$. In this paper, the strong edge geodetic number of complete multipartite graphs is determined. Graphs $G$ with ${\rm sg_e}(G) = n(G)$ are characterized and ${\rm sg_e}$ is determined for Cartesian products $P_n\,\square\, K_m$. The latter result in particular corrects an error from the literature.
Keywords: strong edge geodetic problem, complete multipartite graph, edge-coloring, Cartesian product of graphs
Published in DiRROS: 19.02.2024; Views: 153; Downloads: 52
Full text (430,75 KB)
This document has many files! More...
