DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

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


Authors:

M. Mezzini

Title:

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

Source:

Discussiones Mathematicae Graph Theory

Received: 2019-07-19, Revised: 2019-12-05, Accepted: 2019-12-17, https://doi.org/10.7151/dmgt.2311

Abstract:

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.

Keywords:

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

PDF
Close