Geodesic Transversal of Hypercube and Butterfly networks

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.