The geodesic-transversal problem

DOI10.1016/J.AMC.2021.126621MaRDI QIDQ6358653arXivFDO

Authors Paul Manuel, Boštjan Brešar, Sandi Klavžar

Publication date 20 January 2021

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: A maximal geodesic in a graph is a geodesic (alias shortest path) which is not a subpath of a longer geodesic. The geodesic-transversal problem in a graph $G$ is introduced as the task to find a smallest set $S$ of vertices of $G$ such that each maximal geodesic has at least one vertex in $S$. The minimum cardinality of such a set is the geodesic-transversal number $mgt(G)$ of $G$. It is proved that $mgt(G)=1$ if and only if $G$ is a subdivided star and that the geodesic-transversal problem is NP-complete. Fast algorithms to determine the geodesic-transversal number of trees and of spread cactus graphs are designed, respectively.

This page was built for publication: The geodesic-transversal problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6358653)