Strong edge geodetic problem in networks

• Autorzy: Paul Manuel , Sandi Klavžar , Antony Xavier , Andrew Arokiaraj , Elizabeth Thomas
• Języki publikacji: EN

Abstrakty

EN

Geodesic covering problems form a widely researched topic in graph theory. One such problem is geodetic problem introduced by Harary et al. [Math. Comput. Modelling, 1993, 17, 89-95]. 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.

Słowa kluczowe

EN

Geodetic problem; Strong edge geodetic problem; Computational complexity; Transport networks

Kategorie tematyczne

• 05C12: Distance in graphs
• 05C70: Factorization, matching, partitioning, covering and packing

• Wydawca: De Gruyter Open
• Czasopismo: Open Mathematics
• Rocznik: 2017
• Tom: 15
• Numer: 1
• Strony: 1225-1235

Daty

wydano

2017-01-01

otrzymano

2017-02-15

zaakceptowano

2017-08-16

online

2017-10-03

Twórcy

autor

Paul Manuel

• , , ,

autor

Sandi Klavžar

• , , , ,

autor

Antony Xavier

• , , ,

autor

Andrew Arokiaraj

• , , ,

autor

Elizabeth Thomas

• , , ,

Identyfikatory

DOI

10.1515/math-2017-0101