The geodesic transversal number of a finite connected simple
graph
is the smallest vertex count of a vertex
set meeting every maximal graph geodesic. A
geodesic is maximal when it is not a proper subpath of a longer shortest path. Its
length need not equal the graph diameter (Manuel
et al. 2022).
For a complete graph with
,
every edge is a maximal geodesic, so
.
A path graph instead has a single maximal geodesic
and transversal number 1.
For the hypercube graph , Chen et al. (2026) proved
for . Here
and
denote the ceiling function
and floor function.