Strong geodetic problem on complete multipartite graphs
DOI:
https://doi.org/10.26493/1855-3974.1725.2e5Keywords:
Geodetic problem, strong geodetic problem, (complete) bipartite graphs, (complete) multipartite graphsAbstract
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.Downloads
Published
2019-11-13
Issue
Section
Articles
License
Articles in this journal are published under Creative Commons Attribution 4.0 International License
https://creativecommons.org/licenses/by/4.0/