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$.
翻译：一个图形的大地测量覆盖物,也称为几何路径覆盖物,是一个图形的一组大地测量物,覆盖了图的顶部。一个图形的边缘大地测量物覆盖物是一组覆盖图边缘的大地测量物。一个图形的大地测量物覆盖物数是最小(边缘)大地测量物覆盖物的最基本特征。一个图形的(边缘)大地测量物覆盖物覆盖物问题在于找到图的(边缘)大地测量物覆盖物编号。奇怪的是,对于大多数情况,这些问题只有部分的解决办法。在本文中,我们证明美元维的蝴蝶的大地测量物覆盖物号为$\lcel(2/3)2 ⁇ r\rcele$,其边缘地理测量物覆盖物号为$2 ⁇ r$。
相关内容
微信扫码咨询专知VIP会员