The geodesic-transversal problem

2021/01/20 by Manuel, Paul, Brešar, Boštjan, Klavžar, Sandi · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2101.08042

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 \rm gt(G) of G. It is proved that \rm gt(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.

Cited by

• Distance-based (and path-based) covering problems for graphs of given cyclomatic number

Related

• The geodesic transversal problem on some networks
• Geodesic packing in graphs
• Enumerating all geodesics
• Algorithms and complexity for geodetic sets on planar and chordal graphs
• Strong geodetic problem in grid like architectures