Geodesic packing in graphs

DOI10.1016/J.AMC.2023.128277arXiv2210.15325OpenAlexW4385962665MaRDI QIDQ6095044FDOQ6095044

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)

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.

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

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

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)

Cites Work

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

Cited In (3)

• Title not available (Why is that?)
• The geodesic transversal problem on some networks
• Title not available (Why is that?)

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)