2022/10/27 by Paul Manuel, Manuel, Paul, Boštjan Brešar +3
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2210.15325
openalex publication_date 2022/10/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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, \gt(G), which is the minimum cardinality of a set of vertices that hit all maximal geodesics in G. While \gt(G)≥ \gpack(G) in every graph G, the quotient \rm gt(G)/\rm 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\rm gt(G)\rm gpack(G)≤ C would hold for all graphs G. If T is a tree, then it is proved that \rm gpack(T) = \rm gt(T), and a linear algorithm for determining \rm gpack(T) is derived. The geodesic packing number is also determined for the strong product of paths.