Geodesic
Strong Geodetic Problem in Networks
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 1, pp. 307-321

Voir la notice de l'article provenant de la source Library of Science

In order to model certain social network problems, the strong geodetic problem and its related invariant, the strong geodetic number, are introduced. The problem is conceptually similar to the classical geodetic problem but seems intrinsically more difficult. The strong geodetic number is compared with the geodetic number and with the isometric path number. It is determined for several families of graphs including Apollonian networks. Applying Sierpiński graphs, an algorithm is developed that returns a minimum path cover of Apollonian networks corresponding to the strong geodetic number. It is also proved that the strong geodetic problem is NP-complete.
Keywords: geodetic problem, strong geodetic problem, Apollonian networks, Sierpiński graphs, computational complexity 
@article{DMGT_2020_40_1_a20,
     author = {Manuel, Paul and Klav\v{z}ar, Sandi and Xavier, Antony and Arokiaraj, Andrew and Thomas, Elizabeth},
     title = {Strong {Geodetic} {Problem} in {Networks}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {307--321},
     publisher = {mathdoc},
     volume = {40},
     number = {1},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a20/}
}
TY  - JOUR
AU  - Manuel, Paul
AU  - Klavžar, Sandi
AU  - Xavier, Antony
AU  - Arokiaraj, Andrew
AU  - Thomas, Elizabeth
TI  - Strong Geodetic Problem in Networks
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 307
EP  - 321
VL  - 40
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a20/
LA  - en
ID  - DMGT_2020_40_1_a20
ER  - 
%0 Journal Article
%A Manuel, Paul
%A Klavžar, Sandi
%A Xavier, Antony
%A Arokiaraj, Andrew
%A Thomas, Elizabeth
%T Strong Geodetic Problem in Networks
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 307-321
%V 40
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a20/
%G en
%F DMGT_2020_40_1_a20
Manuel, Paul; Klavžar, Sandi; Xavier, Antony; Arokiaraj, Andrew; Thomas, Elizabeth. Strong Geodetic Problem in Networks. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 1, pp. 307-321. http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a20/