Geodesic packing in graphs

DOI10.1016/J.AMC.2023.128277MaRDI QIDQ6095044zbMATH OpenOpenAlexFDO

Authors Paul Manuel, Boštjan Brešar, Sandi Klavžar

Publication date 11 October 2023

Published in Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2210.15325

zbMATH Keywords

computational complexityRook's graphgeodesic transversaldiagonal gridgeodesic packing

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distance in graphs (05C12)

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, $gt(G)$, which is the minimum cardinality of a set of vertices that hit all maximal geodesics in $G$. While $gt(G)gegpack(G)$ in every graph $G$, the quotient $mgt(G)/mgpack(G)$ is investigated. By using the rook's graph, it is proved that there does not exist a constant $C<3$ such that $fracmgt(G)mgpack(G)leC$ would hold for all graphs $G$. If $T$ is a tree, then it is proved that $mgpack(T)=mgt(T)$, and a linear algorithm for determining $mgpack(T)$ is derived. The geodesic packing number is also determined for the strong product of paths.

Recommendations

• The geodesic-transversal problem
• Some remarks on the geodetic number of a graph
• On The Edge Geodetic Number Of A Graph
• scientific article; zbMATH DE number 1156614
• The geodesic transversal problem on some networks

Cites work

• scientific article; zbMATH DE number 3154393 (Why is no real title available?)
• scientific article; zbMATH DE number 508831 (Why is no real title available?)
• Davenport-Schinzel theory of matrices
• Edge-disjoint packing of stars and cycles
• Extension of Vertex Cover and Independent Set in some classes of graphs
• Handbook of product graphs
• Mutual visibility in graphs
• On the Line Graph of the Complete Bipartite Graph
• On the mutual visibility in Cartesian products and triangle-free graphs
• Packing paths perfectly
• Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results
• The complexity of packing edge-disjoint paths
• The geodesic-transversal problem
• The path partition problem and related problems in bipartite graphs

Cited in

(4)

• scientific article; zbMATH DE number 5661174 (Why is no real title available?)
• The geodesic transversal problem on some networks
• On the strong geodeticity in the corona type product of graphs
• scientific article; zbMATH DE number 2166125 (Why is no real title available?)

This page was built for publication: Geodesic packing in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6095044)