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).