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/

[1] M. Atici, Computational complexity of geodetic set, Int. J. Comput. Math. 79 (2002) 587–591. doi:10.1080/00207160210954

[2] J. Bosák, Geodetic graphs, in: Combinatorics Proc. Fifth Hungarian Colloq., Keszthely (1976) Vol. I, Colloq. Math. Soc. János Bolyai 18 (1978) 151–172.

[3] B. Brešar, S. Klavžar and A. Tepeh Horvat, On the geodetic number and related metric sets in Cartesian product graphs, Discrete Math. 308 (2008) 5555–5561. doi:10.1016/j.disc.2007.10.007

[4] B. Brešar, M. Kovše and A. Tepeh, Geodetic sets in graphs, in: Structural Analysis of Complex Networks, Birkhäuser/Springer, New York (2011) 197–218. doi:10.1007/978-0-8176-4789-6_8

[5] G.J. Chang, L.-D. Tong and H.-T. Wang, Geodetic spectra of graphs, European J. Combin. 25 (2004) 383–391. doi:10.1016/j.ejc.2003.09.010

[6] G. Chartrand, F. Harary, H.C. Swart and P. Zhang, Geodomination in graphs, Bull. Inst. Combin. Appl. 31 (2001) 51–59.

[7] G. Chartrand, F. Harary and P. Zhang, Geodetic sets in graphs, Discuss. Math. Graph Theory 20 (2000) 129–138. doi:10.7151/dmgt.1112

[8] G. Chartrand, F. Harary and P. Zhang, On the geodetic number of a graph, Networks 39 (2002) 1–6. doi:10.1002/net.10007

[9] G. Chartrand and P. Zhang, The geodetic number of an oriented graph, European J. Combin. 21 (2000) 181–189. doi:10.1006/eujc.1999.0301

[10] M.C. Dourado, F. Protti, D. Rautenbach and J.L. Szwarcfiter, Some remarks on the geodetic number of a graph, Discrete Math. 310 (2010) 832–837. doi:10.1016/j.disc.2009.09.018

[11] T. Ekim, A. Erey, P. Heggernes, P. van’t Hof and D. Meister, Computing minimum geodetic sets of proper interval graphs, Lecture Notes in Comput. Sci. 7256 (2012) 279–290. doi:10.1007/978-3-642-29344-3_24

[12] A. Estrada-Moreno, J.A. Rodríguez-Velázquez and E.D. Rodríquez-Bazan, On generalized Sierpiński graphs, Discuss. Math. Graph Theory 37 (2017) 547–560. doi:10.7151/dmgt.1945

[13] M.G. Everett and S.B. Seidman, The hull number of a graph, Discrete Math. 57 (1985) 217–223. doi:10.1016/0012-365X(85)90174-8

[14] A. Farrugia, Orientable convexity, geodetic and hull numbers in graphs, Discrete Appl. Math. 148 (2005) 256–262. doi:10.1016/j.dam.2005.03.002

[15] S.L. Fitzpatrick, The isometric path number of the Cartesian product of paths, Congr. Numer. 137 (1999) 109–119.

[16] M.R. Garey and D.S. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness (W.H. Freeman & Co., New York, NY, 1990).

[17] A. Goldner and F. Harary, Note on a smallest non-Hamiltonian maximal planar graph, Bull. Malays. Math. Sci. Soc. 6 (1975) 41–42.

[18] V.M. Goudar, K.S. Ashalatha, Venkatesha and M.H. Muddebihal, On the geodetic number of line graph, Int. J. Contemp. Math. Sci. 7 (2012) 2289–2295.

[19] P. Hansen and N. van Omme, On pitfalls in computing the geodetic number of a graph, Optim. Lett. 1 (2007) 299–307. doi:10.1007/s11590-006-0032-3

[20] F. Harary, E. Loukakis and C. Tsouros, The geodetic number of a graph, Math. Comput. Modelling 17 (1993) 89–95. doi:10.1016/0895-7177(93)90259-2

[21] A.M. Hinz, K. Klavžar, U. Milutinović, D. Parisse and C. Petr, Metric properties of the Tower of Hanoi graphs and Stern’s diatomic sequence, European J. Combin. 26 (2005) 693–708. doi:10.1016/j.ejc.2004.04.009

[22] A.M. Hinz, S. Klavžar, U. Milutinović and C. Petr, The Tower of Hanoi—Myths and Maths (Birkhäuser/Springer, Basel, 2013).

[23] A.M. Hinz, S. Klavžar and S.S. Zemljič, A survey and classification of Sierpiński-type graphs, Discrete Appl. Math. 217 (2017) 565–600. doi:10.1016/j.dam.2016.09.024

[24] A. Hansberg and L. Volkmann, On the geodetic and geodetic domination numbers of a graph, Discrete Math. 310 (2010) 2140–2146. doi:10.1016/j.disc.2010.04.013

[25] C. Hernando, T. Jiang, M. Mora, I.M. Pelayo and C. Seara, On the Steiner, geodetic and hull numbers of graphs, Discrete Math. 293 (2005) 139–154. doi:10.1016/j.disc.2004.08.039

[26] J.-T. Hung, L.-D. Tong and H.-T. Wang, The hull and geodetic numbers of orientations of graphs, Discrete Math. 309 (2009) 2134–2139. doi:10.1016/j.disc.2008.04.034

[27] V. Iršič, Strong geodetic number of complete bipartite graphs and of graphs with specified diameter, Graphs Combin. 34 (2018) 443–456.

[28] S. Klavžar and U. Milutinović, Graphs S ( n, k ) and a variant of the Tower of Hanoi problem, Czechoslovak Math. J. 47(122) (1997) 95–104.

[29] Y. Liao, Y. Hou and X. Shen, Tutte polynomial of the Apollonian network, J. Stat. Mech., October (2014) P10043. doi:10.1088/1742-5468/2014/10/P10043

[30] P. Manuel, S. Klavžar, A. Xavier, A. Arokiaraj and E. Thomas, Strong edge geodetic problem in networks, Open Math. 15 (2017) 1225–1235. doi:10.1515/math-2017-0101

[31] O. Ore, Theory of Graphs (Amer. Math. Soc., Providence, R.I., 1962). doi:10.1090/coll/038

[32] I.M. Pelayo, Geodesic Convexity in Graphs, Springer Briefs in Mathematics (Springer, New York, 2013). doi:10.1007/978-1-4614-8699-2

[33] G.L. Pellegrini, L. de Arcangelis, H.J. Herrmann and C. Perrone-Capano, Modelling the brain as an Apollonian network (27 Jan 2007). arXiv:q-bio/0701045 [q-bio.NC]

[34] J.A. Solo, R.A. Márquez and L.M. Friedler, Products of geodesic graphs and the geodetic number of products, Discuss. Math. Graph Theory 35 (2015) 35–42. doi:10.7151/dmgt.1774

[35] L.-D. Tong, Geodetic sets and Steiner sets in graphs, Discrete Math. 309 (2009) 4205–4207. doi:10.1016/j.disc.2008.10.010

[36] V.A. VoblyȈı, Enumeration of labeled geodetic planar graphs, Mat. Zametki 97 (2015) 336–341. doi:10.4213/mzm10549

[37] F.-H. Wang, Y.-L. Wang and J.-M. Chang, The lower and upper forcing geodetic numbers of block-cactus graphs, European J. Oper. Res. 175 (2006) 238–245. doi:10.1016/j.ejor.2005.04.026

[38] J. Zhang, W. Sun and G. Xu, Enumeration of spanning trees on Apollonian networks, J. Stat. Mech., September (2013) P09015. doi:10.1088/1742-5468/2013/09/P09015

[39] Z. Zhang, B. Wu and F. Comellas, The number of spanning trees in Apollonian networks, Discrete Appl. Math. 169 (2014) 206–213. doi:10.1016/j.dam.2014.01.015