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

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

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.

• Jezik: Angleški jezik
• Ključne besede: strong edge geodetic problem, complete multipartite graph, edge-coloring, Cartesian product of graphs
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Datum objave: 01.02.2024
• Leto izida: 2024
• Št. strani: 13 str.
• Številčenje: Vol. 50, iss. 1, article no. 13
• PID: 20.500.12556/RUL-154510
• UDK: 519.17
• ISSN pri članku: 1018-6301
• DOI: 10.1007/s41980-023-00849-6
• COBISS.SI-ID: 183235331
• Datum objave v RUL: 19.02.2024

Gradivo je del revije

• Naslov: Bulletin of the Iranian Mathematical Society
• Skrajšan naslov: Bull. iran. math. soc.
• Založnik: Iranian Mathematical Society
• ISSN: 1018-6301
• COBISS.SI-ID: 518040345

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.

Sekundarni jezik

• Jezik: Slovenski jezik
• Ključne besede: krepko povezavno-geodetski problem, polni multipartitini graf, barvanje povezav, kartezični produkt grafov