Geodesic packing in graphs

Abstract

Given a graph $G$, a geodesic packing in $G$ is a set of vertex-disjoint maximal geodesics, and the geodesic packing number of $G$, ${\gpack}(G)$, is the maximum cardinality of a geodesic packing in $G$. It is proved that the decision version of the geodesic packing number is NP-complete. We also consider the geodesic transversal number, $>(G)$, which is the minimum cardinality of a set of vertices that hit all maximal geodesics in $G$. While $\gt(G)\ge \gpack(G)$ in every graph $G$, the quotient $\mathrm{gt}(G)/\mathrm{gpack}(G)$ is investigated. By using the rook's graph, it is proved that there does not exist a constant $C<3$ such that $\frac{\mathrm{gt}(G)}{\mathrm{gpack}(G)}\le C$ would hold for all graphs $G$. If $T$ is a tree, then it is proved that $\mathrm{gpack}(T)=\mathrm{gt}(T)$, and a linear algorithm for determining $\mathrm{gpack}(T)$ is derived. The geodesic packing number is also determined for the strong product of paths.