2018/06/01 by Vesna Iršič, Iršič, Vesna, Matjaž Konvalinka +1
Mathematics · #05C12 #05C70 #68Q17 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C12 #msc:05C70 #msc:68Q17
paper · pdf · doi:10.48550/arxiv.1806.00302
15 pages, 1 figure, 2 tables
arxiv created 2018/06/01 · arxiv updated 2018/06/04
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; in particular, we discuss its asymptotic behavior. 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.