论文标题
蝴蝶网络的大地覆盖问题
The geodesic cover problem for butterfly networks
论文作者
论文摘要
图形的地理覆盖物，也称为等距路径盖，是一组覆盖图的顶点集的大地测量学。图形的边缘地球盖是一组覆盖图的边缘集的大地测量学。图形的测量（边缘）盖子数是最小（边缘）测量盖的基数。图形的（边缘）测量盖问题是找到图形的（边缘）测量盖号。令人惊讶的是，对于大多数情况，只有针对这些问题的部分解决方案。在本文中，我们证明了$ r $二维蝴蝶的大地覆盖号为$ \ lceil（2/3）2^r \ rceil $，其边缘地球封面封面号为$ 2^r $。
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$.
