.png){kind=icon}
.png){kind=icon}
Return
Geodesic packing in graphs
.png){kind=icon}
PRE
AI
DOI：10.1016/j.amc.2023.128277.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
A geodesic packing of a graph.. is a set of vertex-disjoint maximal geodesics. The maximum cardinality of a geodesic packing is the geodesic packing number gpack(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 gt(G)/gpack(G) is investigated. By using the rook's graph, it is proved that there does not exist a constant C < 3 such that gt(G) / gpack(G) <= C would hold for all graphs G. If Tau is a tree, then it is proved that gpack(Tau) = g(Tau), and a linear algorithm for determining gpack(Tau) is derived. The geodesic packing number is also determined for the strong product of paths.
Keywords:
Geodesic packing
Geodesic transversal
Computational complexity
Rook's graph
Diagonal grid
Journal
IF:
3.4
Papers:
2.3W
Citations:
3.3W