Metraipolis › archive › dc_d7c73bbdea45
Geodesic Transversal of Hypercube and Butterfly networks — arXiv:2611.06107
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.06107
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-05T18:28:27.871Z
- SHA-256 of the archived text
68cde3f21aaf6167ce0c78277976383ad712f13260d850ece7c9c8877c40aacb- Stable URL of this page
https://metraipolis.com/documento/dc_d7c73bbdea45
How to cite
Geodesic Transversal of Hypercube and Butterfly networks — arXiv:2611.06107 — arXiv (en), https://arxiv.org/abs/2611.06107 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d7c73bbdea45 (Metraipolis archive dc_d7c73bbdea45, sha256 68cde3f21aaf6167ce0c78277976383ad712f13260d850ece7c9c8877c40aacb)
BibTeX
@misc{dcd7c73bbdea45,
title = {Geodesic Transversal of Hypercube and Butterfly networks — arXiv:2611.06107},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.06107},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d7c73bbdea45; sha256 68cde3f21aaf6167ce0c78277976383ad712f13260d850ece7c9c8877c40aacb},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.06107. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 its induced subgraphs. Using this lemma, we determine the gt-number of Butterfly and Hypercube networks. Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno). Categorie arXiv: Combinatorics (math.CO). Pagina del lavoro: https://arxiv.org/abs/2611.06107 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-11-05T18:18:33.997Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).