357 KB26 KB200820252019Iršič, VesnaKonvalinka, Matjažletnik:17številka:2str. 481-491ISSN:1855-3966COBISSID_HOST:18796121URN:URN:NBN:SI:doc-C0WY5SN0enUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporanea(complete) bipartite graphs(complete) multipartite graphs(polni) dvodelni graf(polni) večdelni grafgeodetic problemgeodetski problemkrepki geodetski problemstrong geodetic problemStrong geodetic problem on complete multipartite graphs|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-completePri krepkem geodetskem problemu moramo poiskati najmanjše število vozlišč, tako da z izborom ene najkrajše poti med vsakim parom vozlišč pokrijemo vsa vozlišča grafa. V tem članku preučujemo krepko geodetsko število na polnih dvodelnih grafih. Izpeljemo tudi nekatere rezultate za polne večdelne grafe. Dokažemo tudi, da je krepki geodetski problem na (spošnih) dvodelnih grafih NP-polnTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije