Article in volume
Authors:
Title:
An $O(mn^2)$ algorithm for computing the strong geodetic number in outerplanar graphs
PDFSource:
Discussiones Mathematicae Graph Theory 42(2) (2022) 591-599
Received: 2019-07-19 , Revised: 2019-12-16 , Accepted: 2019-12-17 , Available online: 2020-03-10 , 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 $Γ(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(Γ(S))=
\bigcup_{\gamma[x,y] \in Γ(S) } V(\gamma[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
References:
- B. Allgeier, Structure and Properties of Maximal Outerplanar Graphs, Doctoral Thesis (University of Louisville, 2009).
https://doi.org/10.18297/edtB3 - A. Arokiaraj, S. Klavžar, P. Manuel, E. Thomas and A. Xavier, Strong geodetic problems in networks, Discuss. Math. Graph Theory 40 (2020) 307–321.
https://doi.org/10.7151/dmgt.2139 - M. Atici, Computational complexity of geodetic set, Int. J. Comput. Math. 79 (2002) 587–591.
https://doi.org/10.1080/00207160210954 - M.C. Dourado, J.G. Gimbel, J. Kratochvíl, F. Protti and J.L. Szwarcfiter, On the computation of the hull number of a graph, Discrete Math. 309 (2009) 5668–5674.
https://doi.org/10.1016/j.disc.2008.04.020 - M.C. Dourado, F. Protti, D. Rautenbach and J.L. Szwarcfiter, Some remarks on the geodetic number of a graph, Discrete Math. 310 (2010) 832–837.
https://doi.org/10.1016/j.disc.2009.09.018 - T. Ekim and A. Erey, Block decomposition approach to compute a minimum geodetic set, RAIRO Oper. Res. 48 (2014) 497–507.
https://doi.org/10.1051/ro/2014019 - M. Farber and R.E. Jamison, Convexity in graphs and hypergraphs, SIAM J. Algebraic Discrete Methods 7 (1986) 433–444.
https://doi.org/10.1137/0607049 - V. Gledel and V. Iršič, Strong geodetic number of complete bipartite graphs, crown graphs and hypercubes, Bull. Malays. Math. Sci. Soc. 43 (2020) 2737–2767.
https://doi.org/10.1007/s40840-019-00833-6 - V. Gledel, V. Iršič and S. Klavžar, Strong geodetic cores and Cartesian product graphs, Appl. Math. Comput. 363 (2019) 124609.
https://doi.org/10.1016/j.amc.2019.124609 - F. Harary, Graph Theory (Addison-Wesley, Reading, 1991).
- V. Iršič, Strong geodetic number of complete bipartite graphs and of graphs with specified diameter, Graphs Combin. 34 (2018) 443–456.
https://doi.org/10.1007/s00373-018-1885-9 - V. Iršič and S. Klavžar, Strong geodetic problem on Cartesian products of graphs, RAIRO Oper. Res. 52 (2018) 205–216.
https://doi.org/10.1051/ro/2018003 - S. Klavžar and P. Manuel, Strong geodetic problem in grid-like architectures, Bull. Malays. Math. Sci. Soc. 41 (2018) 1671–1680.
https://doi.org/10.1007/s40840-018-0609-x - F.M. Malvestuto, M. Mezzini and M. Moscarini, Computing simple-path convex hulls in hypergraphs, Inform. Process. Lett. 111 (2011) 231–234.
https://doi.org/10.1016/j.ipl.2010.11.026 - P. Manuel, S. Klavžar, A. Xavier, A. Arokiaraj and E. Thomas, Strong edge geodetic problem in networks, Open Math. 15 (2017) 1225–1235.
https://doi.org/10.1515/math-2017-0101 - M. Mezzini, On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs, Theoret. Comput. Sci. 411 (2010) 1212–1220.
https://doi.org/10.1016/j.tcs.2009.12.017 - M. Mezzini, On the geodetic iteration number of the contour of a graph, Discrete Appl. Math. 206 (2016) 211–214.
https://doi.org/10.1016/j.dam.2016.02.012 - M. Mezzini, Polynomial time algorithm for computing a minimum geodetic set in outerplanar graphs, Theoret. Comput. Sci. 745 (2018) 63–74.
https://doi.org/10.1016/j.tcs.2018.05.032 - M. Mezzini and M. Moscarini, On the geodeticity of the contour of a graph, Discrete Appl. Math. 181 (2015) 209–220.
https://doi.org/10.1016/j.dam.2014.08.028 - M. Mezzini and M. Moscarini, The contour of a bridged graph is geodetic, Discrete Appl. Math. 204 (2016) 213–215.
https://doi.org/10.1016/j.dam.2015.10.007 - S.L. Mitchell, Linear algorithms to recognize outerplanar and maximal outerplanar graphs, Inform. Process. Lett. 9 (1979) 229–232.
https://doi.org/10.1016/0020-0190(79)90075-9 - I.M. Pelayo, Geodesic Convexity in Graphs (Springer, New York, NY, 2013).
https://doi.org/10.1007/978-1-4614-8699-2 - M.M. Sysło, Characterizations of outerplanar graphs, Discrete Math. 26 (1979) 47–53.
https://doi.org/10.1016/0012-365X(79)90060-8
Close