The geodesic-transversal problem

DOI10.1016/J.AMC.2021.126621arXiv2101.08042MaRDI QIDQ6358653FDOQ6358653

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

Publication date: 20 January 2021

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.

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)

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)