Geodesic
An O(mn2) Algorithm for Computing the Strong Geodetic Number in Outerplanar Graphs
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 2, pp. 591-599

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

Let G = (V (G), E(G)) be a graph and S be a subset of vertices of G. Let us denote by γ [u, v] a geodesic between u and v. Let Γ(S) = { γ [ v_i, v_j ] | v_i, v_j ∈ S be a set of exactly |S|(|S|−1) // 2 geodesics, one for each pair of distinct vertices in S. Let V ( Γ (S)) = ⋃_γ [x,y] ∈Γ (S) V ( γ [x, y]) be the set of all vertices contained in all the geodesics in Γ (S). If V ( Γ (S)) = V (G) for some Γ (S), then we say that S is a strong geodetic set of G. The cardinality of a minimum strong geodetic set of a graph is the strong geodetic number of G. It is known that it is NP-hard to determine the strong geodetic number of a general graph. In this paper we show that the strong geodetic number of an outerplanar graph can be computed in polynomial time.
Keywords: outerplanar graph, strong geodetic set, strong geodetic number, geodetic set, geodetic number, geodesic convexity 
Mezzini, Mauro. An O(mn2) Algorithm for Computing the Strong Geodetic Number in Outerplanar Graphs. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 2, pp. 591-599. http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a14/
@article{DMGT_2022_42_2_a14,
     author = {Mezzini, Mauro},
     title = {An {O(mn\protect\textsuperscript{2})} {Algorithm} for {Computing} the {Strong} {Geodetic} {Number} in {Outerplanar} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {591--599},
     year = {2022},
     volume = {42},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a14/}
}
TY  - JOUR
AU  - Mezzini, Mauro
TI  - An O(mn2) Algorithm for Computing the Strong Geodetic Number in Outerplanar Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 591
EP  - 599
VL  - 42
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a14/
LA  - en
ID  - DMGT_2022_42_2_a14
ER  - 
%0 Journal Article
%A Mezzini, Mauro
%T An O(mn2) Algorithm for Computing the Strong Geodetic Number in Outerplanar Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 591-599
%V 42
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a14/
%G en
%F DMGT_2022_42_2_a14

[1] B. Allgeier, Structure and Properties of Maximal Outerplanar Graphs, Doctoral Thesis (University of Louisville, 2009). https://doi.org/10.18297/edtB3

[2] A. Arokiaraj, S. Klavžar, P. Manuel, E. Thomas and A. Xavier, Strong geodetic problems in networks, Discuss. Math. Graph Theory 40 (2020) 307–321. https://doi.org/10.7151/dmgt.2139

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

[4] M.C. Dourado, J.G. Gimbel, J. Kratochvíl, F. Protti and J.L. Szwarcfiter, On the computation of the hull number of a graph, Discrete Math. 309 (2009) 5668–5674. https://doi.org/10.1016/j.disc.2008.04.020

[5] 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. https://doi.org/10.1016/j.disc.2009.09.018

[6] T. Ekim and A. Erey, Block decomposition approach to compute a minimum geodetic set, RAIRO Oper. Res. 48 (2014) 497–507. https://doi.org/10.1051/ro/2014019

[7] M. Farber and R.E. Jamison, Convexity in graphs and hypergraphs, SIAM J. Algebraic Discrete Methods 7 (1986) 433–444. https://doi.org/10.1137/0607049

[8] V. Gledel and V. Iršič, Strong geodetic number of complete bipartite graphs, crown graphs and hypercubes, Bull. Malays. Math. Sci. Soc. 43 (2020) 2737–2767. https://doi.org/10.1007/s40840-019-00833-6

[9] V. Gledel, V. Iršič and S. Klavžar, Strong geodetic cores and Cartesian product graphs, Appl. Math. Comput. 363 (2019) 124609. https://doi.org/10.1016/j.amc.2019.124609

[10] F. Harary, Graph Theory (Addison-Wesley, Reading, 1991).

[11] V. Iršič, Strong geodetic number of complete bipartite graphs and of graphs with specified diameter, Graphs Combin. 34 (2018) 443–456. https://doi.org/10.1007/s00373-018-1885-9

[12] V. Iršič and S. Klavžar, Strong geodetic problem on Cartesian products of graphs, RAIRO Oper. Res. 52 (2018) 205–216. https://doi.org/10.1051/ro/2018003

[13] S. Klavžar and P. Manuel, Strong geodetic problem in grid-like architectures, Bull. Malays. Math. Sci. Soc. 41 (2018) 1671–1680. https://doi.org/10.1007/s40840-018-0609-x

[14] F.M. Malvestuto, M. Mezzini and M. Moscarini, Computing simple-path convex hulls in hypergraphs, Inform. Process. Lett. 111 (2011) 231–234. https://doi.org/10.1016/j.ipl.2010.11.026

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

[16] M. Mezzini, On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs, Theoret. Comput. Sci. 411 (2010) 1212–1220. https://doi.org/10.1016/j.tcs.2009.12.017

[17] M. Mezzini, On the geodetic iteration number of the contour of a graph, Discrete Appl. Math. 206 (2016) 211–214. https://doi.org/10.1016/j.dam.2016.02.012

[18] M. Mezzini, Polynomial time algorithm for computing a minimum geodetic set in outerplanar graphs, Theoret. Comput. Sci. 745 (2018) 63–74. https://doi.org/10.1016/j.tcs.2018.05.032

[19] M. Mezzini and M. Moscarini, On the geodeticity of the contour of a graph, Discrete Appl. Math. 181 (2015) 209–220. https://doi.org/10.1016/j.dam.2014.08.028

[20] M. Mezzini and M. Moscarini, The contour of a bridged graph is geodetic, Discrete Appl. Math. 204 (2016) 213–215. https://doi.org/10.1016/j.dam.2015.10.007

[21] S.L. Mitchell, Linear algorithms to recognize outerplanar and maximal outerplanar graphs, Inform. Process. Lett. 9 (1979) 229–232. https://doi.org/10.1016/0020-0190(79)90075-9

[22] I.M. Pelayo, Geodesic Convexity in Graphs (Springer, New York, NY, 2013). https://doi.org/10.1007/978-1-4614-8699-2

[23] M.M. Sysłlo, Characterizations of outerplanar graphs, Discrete Math. 26 (1979) 47–53. https://doi.org/10.1016/0012-365X(79)90060-8