The geodesic cover problem for butterfly networks
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909874058690560 |
|---|---|
| author | Manuel, Paul Klavzar, Sandi Prabha, R. Arokiaraj, Andrew |
| author_facet | Manuel, Paul Klavzar, Sandi Prabha, R. Arokiaraj, Andrew |
| contents | A geodesic cover, also known as an isometric path cover, of a graph is a set of geodesics which cover the vertex set of the graph. An edge geodesic cover of a graph is a set of geodesics which cover the edge set of the graph. The geodesic (edge) cover number of a graph is the cardinality of a minimum (edge) geodesic cover. The (edge) geodesic cover problem of a graph is to find the (edge) geodesic cover number of the graph. Surprisingly, only partial solutions for these problems are available for most situations. In this paper we demonstrate that the geodesic cover number of the $r$-dimensional butterfly is $\lceil (2/3)2^r\rceil$ and that its edge geodesic cover number is $2^r$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2210_12675 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | The geodesic cover problem for butterfly networks Manuel, Paul Klavzar, Sandi Prabha, R. Arokiaraj, Andrew Combinatorics Computational Complexity A geodesic cover, also known as an isometric path cover, of a graph is a set of geodesics which cover the vertex set of the graph. An edge geodesic cover of a graph is a set of geodesics which cover the edge set of the graph. The geodesic (edge) cover number of a graph is the cardinality of a minimum (edge) geodesic cover. The (edge) geodesic cover problem of a graph is to find the (edge) geodesic cover number of the graph. Surprisingly, only partial solutions for these problems are available for most situations. In this paper we demonstrate that the geodesic cover number of the $r$-dimensional butterfly is $\lceil (2/3)2^r\rceil$ and that its edge geodesic cover number is $2^r$. |
| title | The geodesic cover problem for butterfly networks |
| topic | Combinatorics Computational Complexity |
| url | https://arxiv.org/abs/2210.12675 |