For a graph  the problem to find a set  where each vertex in  lies on at least two fixed geodesics between the vertices in S, is called the strong doubly geodetic problem and the cardinality of the smallest such S is the strong doubly geodetic number of G. In this paper, the computational complexity for strong doubly geodetic problem is studied and also some bounds for general graphs are derived.

strong geodetic number, strong geodetic set, strong doubly geodetic number, geodetic set.

Received: December 7, 2020; Accepted: January 5, 2021 Published: January 8, 2021

How to cite this article: Deepa Mathew and D. Antony Xavier, Strong doubly geodetic problem on graphs, JP Journal of Algebra, Number Theory and Applications 49(1) (2021), 23-49. DOI: 10.17654/NT049010023

This Open Access Article is Licensed under Creative Commons Attribution 4.0 International License

References:

[1] D. Antony Xavier, Andrew Arokiaraj and Elizabeth Thomas, Doubly geodetic number of a graph, IOSR Journal of Mathematics 12 (2016), 13-17.
[2] D. Antony Xavier, Deepa Mathew and Santiagu Theresal, Strong geodetic domination of graphs, International Journal of Innovative Technology and Exploring Engineering 8(12) (2019), 82-89.
[3] D. Antony Xavier, Deepa Mathew, Santiagu Theresal and Eddith Sarah Varghese, Some results on strong edge geodetic problem in graphs, Communications in Mathematics and Applications 11(3) (2020), 403-413.
[4] L. G. Bino Infanta, D. Antony Xavier and Santiagu Theresal, Strong (2, 2) geodetic number of graphs, AIP Conference Proceedings 2261 (2020), 030054.
[5] G. Chartrand, Frank Harary and Ping Zhang, On the geodetic number of a graph, Networks 39(1) (2002), 1-6.
[6] Gerard J. Chang and George L. Nemhauser, The k-domination and k-stability problems on sun-free chordal graphs, SIAM Journal on Algebraic Discrete Methods 5(3) (1984), 332-345.
[7] Huifen Ge, Zhao Wang and Jinyu Zou, Strong geodetic number in some networks, Journal of Mathematics Research 11(2) (2019), 20-29.
[8] Valentin Gledel and Vesna Iršič, Strong geodetic number of complete bipartite graphs, crown graphs and hypercubes, Bull. Malays. Math. Sci. Soc. 43 (2020), 2757-2767.
[9] Frank Harary, Graph Theory, Addison Wesley Publishing Company, Reading, Massachusetts, 1969.
[10] Frank Harary, Emmanuel Loukakis and Constantine Tsouros, The geodetic number of a graph, Math. Comput. Modelling 17(11) (1993), 89-95.
[11] Adriana Hansberg and Lutz Volkmann, On the geodetic and geodetic domination numbers of a graph, Discrete Math. 310(15-16) (2010), 2140-2146.
[12] Vesna Iršič, Strong geodetic number of complete bipartite graphs and of graphs with specified diameter, Graphs Combin. 34(3) (2018), 443-456.
[13] Vesna Iršič and Matjaz Konvalinka, Strong geodetic problem on complete multipartite graphs, Ars Math. Contemp. 17(2) (2019), 481-491.
[14] Vesna Iršič and Sandi Klavzar, Strong geodetic problem on Cartesian products of graphs, RAIRO Oper. Res. 52(1) (2018), 205-216.
[15] Sandi Klavzar and Paul Manuel, Strong geodetic problem in grid-like architectures, Bull. Malays. Math. Sci. Soc. 41(3) (2018), 1671-1680.
[16] Derek Kiser, Distance-2 domatic numbers of graphs, Electronic Theses and Dissertations, 2015.
[17] Mathieu Liedloff, Finding a dominating set on bipartite graphs, Information Processing Letters 107(5) (2008), 154-157.
[18] 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.
[19] Paul Manuel, Sandi Klavžar, Antony Xavier, Andrew Arokiaraj and Elizabeth Thomas, Strong geodetic problem in networks, Discuss. Math. Graph Theory 40(1) (2020), 307-321.
[20] Paul Manuel, Sandi Klavžar, Antony Xavier, Andrew Arokiaraj and Elizabeth Thomas, Strong edge geodetic problem in networks, Open Math. 15(1) (2017), 1225-1235.
[21] Ignacio M. Pelayo, Geodesic Convexity in Graphs, Springer, New York, 2013.
[22] Kellogg S. Booth and J. Howard Johnson, Dominating sets in chordal graphs, SIAM J. Comput. 11 (1982), 191-199.
[23] Z. Wang, Y. Mao, H. Ge and C. Magnant, Strong geodetic number of graphs and connectivity, Bull. Malays. Math. Sci. Soc. 43 (2020), 2443-2453.
https://doi.org/10.1007/s40840-019-00809-6.
[24] Deepa Mathew, D. Antony Xavier, Santiagu Theresal and Eddith Sarah Varghese, Strong 2-edge geodetic problem in graphs, Discrete Mathematics, Algorithms and Applications (communicated).