Strong edge geodetic problem on complete multipartite graphs and some extremal graphs for the problem

Klavžar, Sandi (author), Zmazek, Eva (author)

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.

• Language: English
• Keywords: strong edge geodetic problem, complete multipartite graph, edge-coloring, Cartesian product of graphs
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Publication date: 01.02.2024
• Year: 2024
• Number of pages: 13 str.
• Numbering: Vol. 50, iss. 1, article no. 13
• PID: 20.500.12556/RUL-154510
• UDC: 519.17
• ISSN on article: 1018-6301
• DOI: 10.1007/s41980-023-00849-6
• COBISS.SI-ID: 183235331
• Publication date in RUL: 19.02.2024

Record is a part of a journal

• Title: Bulletin of the Iranian Mathematical Society
• Shortened title: Bull. iran. math. soc.
• Publisher: Iranian Mathematical Society
• ISSN: 1018-6301
• COBISS.SI-ID: 518040345

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.

Secondary language

• Language: Slovenian
• Keywords: krepko povezavno-geodetski problem, polni multipartitini graf, barvanje povezav, kartezični produkt grafov