Strong geodetic problem on complete multipartite graphs

Authors

  • Vesna Iršič University of Ljubljana, Slovenia and Institute of Mathematics, Physics, and Mechanics, Slovenia
  • Matjaž Konvalinka University of Ljubljana, Slovenia and Institute of Mathematics, Physics, and Mechanics, Slovenia

DOI:

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

Keywords:

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

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.

Downloads

Published

2019-11-13

Issue

Vol. 17 No. 2 (2019)

Section

Articles

License

Articles in this journal are published under Creative Commons Attribution 4.0 International License
https://creativecommons.org/licenses/by/4.0/