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

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.AMC.2021.126621

Mathematics Subject Classification ID

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

arXiv classification

math.CO

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)