无向de Bruijn图和Kautz图的k元控制

The k-Tuple Domination of de Bruijn and Kautz Graphs

在无向图G中,对于正整数k≥1,图G的一个k元控制集D是顶点集V(G)的一个子集,并且使得G中的每一个顶点至少被D中k个点控制.文章给出了在无向de Bruijn图和Kautz图中最小k元控制集的基数.

In an undirected graph,for a positive integer k,a k-tuple dominating set of a graph is a subset D of vertices such that every vertex is dominated by at least k vertices in D.In this paper,we give the minimal k-tuple domination in the undirected de Bruijn graphs and Kautz graphs.