ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


M. Mezzini


An $O(mn^2)$ algorithm for computing the strong geodetic number in outerplanar graphs


Discussiones Mathematicae Graph Theory

Received: 2019-07-19, Revised: 2019-12-05, Accepted: 2019-12-17,


Let $G=(V(G),E(G))$ be a graph and $S$ be a subset of vertices of $G$. Let us denote {by} $\gamma[u,v]$ a geodesic between $u$ and $v$. Let $\Gamma(S) = \{\gamma[v_i,v_j] \,|\, v_i , v_j \in S\}$ be a set of exactly $|S| (|S|-1)/2$ geodesics, one for each pair of distinct vertices in $S$. Let $V(\Gamma(S))= \bigcup_{\gamma[x,y] \in \Gamma(S) } V(\gamma[x,y])$ be the set of all vertices contained in all the geodesics in $\Gamma(S)$. If $V(\Gamma(S))=V(G)$ for some $\Gamma(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.


outerplanar graph, strong geodetic set, strong geodetic number, geodetic set, geodetic number, geodesic convexity