20.500.12556/DKUM-68859 Strong edge geodetic problem in networks Krepki povezavno-geodetski problem v omrežjih Geodesic covering problems form a widely researched topic in graph theory. One such problem is geodetic problem introduced by Harary et al. Here we introduce a variation of the geodetic problem and call it strong edge geodetic problem. We illustrate how this problem is evolved from social transport networks. It is shown that the strong edge geodetic problem is NP-complete. We derive lower and upper bounds for the strong edge geodetic number and demonstrate that these bounds are sharp. We produce exact solutions for trees, block graphs, silicate networks and glued binary trees without randomization. Problemi geodetskih pokrivanj tvorijo obsežno raziskovalno področje v teoriji grafov. Eden izmed njih je geodetski problem, ki so ga vpeljali Harary in drugi. V tem članku vpeljemo inačico geodetskega problema, ki jo poimenujemo krepki povezavno-geodetski problem. Opišemo, kako je bil ta problem porojen iz socialnih transportnih omrežij. Dokažemo, da je krepki povezavno-geodetski problem NP-poln. Izpeljemo spodnje in zgornje meje za krepko povezavno-geodetsko število in pokažemo, da so meje tesne. Dokažemo tudi točne vrednosti za drevesa, bločne grafe, silikatna omrežja in zlepljena binarna drevesa brez slučajnosti. geodetic problem strong edge geodetic problem computational complexity transport networks geodetski problem krepki povezavno-geodetski problem računska zahtevnost transportno omrežje true true true De Gruyter Angleški jezik Slovenski jezik Znanstveno delo 2017-11-03 12:04:33 2017-11-03 12:05:33 2026-09-24 12:11:32 2019-07-11 17:12:48 2017 0 0 10 str. št. 1 Letn. 15 2017 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 2017-02-15 2017-08-16 Y508-704X 519.17 17824345 18142553 10.1515/math-2017-0101 Y508-704X URN:SI:UM:DK:W5ZNBWRO Open_Mathematics_2017_Manuel_et_al._Strong_edge_geodetic_problem_in_networks.pdf Open_Mathematics_2017_Manuel_et_al._Strong_edge_geodetic_problem_in_networks.pdf 1 BFB598C40E4C2D53DB19480118EC7830 1b2be06f570265585ab31f670c99118c011148fc3ecb9eb01d35deafe1f581f4 7838d7d2-7c0f-11eb-bb7a-00155d0001ca 20.500.12556/dkum/03439a33-ee05-49d6-b841-054e77141093 https://dk.um.si/Dokument.php?lang=slv&id=120001 http://www.degruyter.com/view/j/math.2017.15.issue-1/math-2017-0101/math-2017-0101.xml 1 https://dk.um.si/Dokument.php?lang=slv&id=120000 Fakulteta za naravoslovje in matematiko 0 0 0