Geodesic Transversal of Hypercube and Butterfly networks

@misc{prabha2026geodesic,
  title = {{Geodesic Transversal of Hypercube and Butterfly networks}},
  author = {R. Prabha and B. Sandhiya and Paul Manuel},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.06107},
  eprint = {2611.06107},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.06107},
}

TY  - UNPB
TI  - Geodesic Transversal of Hypercube and Butterfly networks
AU  - R. Prabha
AU  - B. Sandhiya
AU  - Paul Manuel
PY  - 2026
DA  - 2026/11/04
PB  - arXiv
DO  - 10.48550/arxiv.2611.06107
UR  - https://arxiv.org/abs/2611.06107
AB  - 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⊆ 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 its induced subgraphs. Using this lemma, we determine the gt-number of Butterfly and Hypercube networks.
ER  -