×

Strong geodetic problem in networks. (English) Zbl 1430.05028

Summary: 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.

MSC:

05C12 Distance in graphs
05C82 Small world graphs, complex networks (graph-theoretic aspects)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
91D30 Social networks; opinion dynamics
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] M. Atici, Computational complexity of geodetic set, Int. J. Comput. Math. 79 (2002) 587-591. doi:10.1080/00207160210954; · Zbl 0999.05027
[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; · Zbl 1200.05060
[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; · Zbl 1221.05107
[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; · Zbl 1034.05018
[6] G. Chartrand, F. Harary, H.C. Swart and P. Zhang, Geodomination in graphs, Bull. Inst. Combin. Appl. 31 (2001) 51-59.; · Zbl 0969.05048
[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; · Zbl 0958.05044
[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; · Zbl 0987.05047
[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; · Zbl 0941.05033
[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; · Zbl 1209.05129
[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; · Zbl 1353.68119
[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; · Zbl 1366.05090
[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; · Zbl 1066.05061
[15] S.L. Fitzpatrick, The isometric path number of the Cartesian product of paths, Congr. Numer. 137 (1999) 109-119.; · Zbl 0968.05043
[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).; · Zbl 0411.68039
[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.; · Zbl 1273.05039
[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; · Zbl 1152.05337
[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; · Zbl 0825.68490
[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; · Zbl 1060.05007
[22] A.M. Hinz, S. Klavžar, U. Milutinović and C. Petr, The Tower of Hanoi—Myths and Maths (Birkhäuser/Springer, Basel, 2013).; · Zbl 1285.00003
[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; · Zbl 1358.05219
[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; · Zbl 1219.05119
[25] 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; · Zbl 1152.05337
[26] 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; · Zbl 1062.05052
[27] 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; · Zbl 1208.05037
[28] V. Iršič, Strong geodetic number of complete bipartite graphs and of graphs with specified diameter, Graphs Combin. 34 (2018) 443-456.; · Zbl 1388.05054
[29] 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.; · Zbl 0898.05042
[30] 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; · Zbl 1456.05082
[31] 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; · Zbl 1375.05074
[32] O. Ore, Theory of Graphs (Amer. Math. Soc., Providence, R.I., 1962). doi:10.1090/coll/038; · Zbl 0105.35401
[33] I.M. Pelayo, Geodesic Convexity in Graphs, Springer Briefs in Mathematics (Springer, New York, 2013). doi:10.1007/978-1-4614-8699-2; · Zbl 1285.05001
[34] 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];
[35] 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; · Zbl 1307.05063
[36] L.-D. Tong, Geodetic sets and Steiner sets in graphs, Discrete Math. 309 (2009) 4205-4207. doi:10.1016/j.disc.2008.10.010; · Zbl 1190.05060
[37] V.A. VoblyȈı, Enumeration of labeled geodetic planar graphs, Mat. Zametki 97 (2015) 336-341. doi:10.4213/mzm10549;
[38] 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; · Zbl 1137.05315
[39] 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; · Zbl 1456.05161
[40] 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; · Zbl 1288.05066
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.