Strong edge geodetic problem in networks

• DOI: 10.1515/math-2017-0101
• Publication Date: 2017-10-06T10:01:56Z
• Authors: Paul Manuel; Sandi Klavžar; Antony Xavier; Andrew Arokiaraj; Elizabeth Thomas
• Keywords: transportno omrežje; computational complexity; 05c70; krepki povezavno-geodetski problem; računska zahtevnost; 0102 computer and information sciences; 01 natural sciences; info:eu-repo/classification/udc/519.17; geodetic problem; QA1-939; geodetski problem; 05c12; strong edge geodetic problem; transport networks; Mathematics

Abstract Geodesic covering problems form a widely researched topic in graph theory. One such problem is geodetic introduced by Harary et al. [Math. Comput. Modelling, 1993, 17, 89-95]. Here we introduce variation of the and call it strong edge problem. We illustrate how this evolved from social transport networks. It shown that NP-complete. derive lower upper bounds for number demonstrate these are sharp. produce exact solutions trees, block graphs, silicate networks glued binary trees without randomization.