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 
@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},
     publisher = {mathdoc},
     volume = {42},
     number = {2},
     year = {2022},
     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
PB  - mathdoc
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
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a14/
%G en
%F DMGT_2022_42_2_a14
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/

[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