An O(mn2) Algorithm for Computing the Strong Geodetic Number in Outerplanar Graphs

Discussiones Mathematicae Graph Theory

Mezzini Mauro¹ 

[1] Department of Education, Roma Tre University;

关键词: outerplanar graph;    strong geodetic set;    strong geodetic number;    geodetic set;    geodetic number;    geodesic convexity;    05c10;    05c12;   

DOI  :  10.7151/dmgt.2311

来源: DOAJ

【 摘 要 】

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) = {γ[vi, vj] | vi, vj ∈ 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.

【 授权许可】

Unknown