Geodesic Transversal Number

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.