- Tytuł:
- An O(mn2) Algorithm for Computing the Strong Geodetic Number in Outerplanar Graphs
- Autorzy:
- Mezzini, Mauro
- Powiązania:
- https://bibliotekanauki.pl/articles/32317585.pdf
- Data publikacji:
- 2022-05-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
outerplanar graph
strong geodetic set
strong geodetic number
geodetic set
geodetic number
geodesic convexity - Opis:
- 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) = \{ γ [ 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2022, 42, 2; 591-599
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł