Geodesic Transversal of Hypercube and Butterfly networks
Source: arxiv.org/abs/2611.06107
A geodesic $P$ of a connected graph $G(V,E)$ is called a maximal geodesic if there exists no geodesic $P'$ in $G$ that contains $P$ as its sub-path. The geodesic transversal problem determines a subset $S\subseteq V(G)$ such that every possible maximal geodesic of $G$ includes at least one vertex of $S$. Such a set with minimum number of elements is called a gt-set and its cardinality is the gt-number of $G$. In this paper, we establish a general result, called the Geodesic Transversal lemma which provides a lower bound for the gt-number of an arbitrary graph $G$ in terms of the gt-number of…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.06107
curl -X POST /api/v1/records/arxiv/2611.06107/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.06107/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'