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/