Strong geodetic problem on complete multipartite graphs

Vesna Iršič, Matjaž Konvalinka

Abstract


The strong geodetic problem is to find the smallest number of vertices such that by fixing one shortest path between each pair, all vertices of the graph are covered. In this paper we study the strong geodetic problem on complete bipartite graphs. Some results for complete multipartite graphs are also derived. Finally, we prove that the strong geodetic problem restricted to (general) bipartite graphs is NP-complete.

Keywords


Geodetic problem, strong geodetic problem, (complete) bipartite graphs, (complete) multipartite graphs

Full Text:

PDF


DOI: https://doi.org/10.26493/1855-3974.1725.2e5

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications