On two problems concerning the geodesic transversal number of graphs
math.CO
Submitted: 2026-10-29
Updated: 2026-10-29
Comments: 10 pages
License: http://creativecommons.org/licenses/by/4.0/
The gist: We establish sharp upper and lower bounds on the geodesic transversal number of hypercubes.
Abstract
We establish sharp upper and lower bounds on the geodesic transversal number of hypercubes. We also obtain a lower bound on the geodesic transversal number of Hamming graphs. As applications, we provide negative answers to two open problems concerning the geodesic transversal number.
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality