The k-tuple twin domination in de Bruijn and Kautz digraphs
The k-tuple twin domination in de Bruijn and Kautz digraphs
复制标题
DOI：
10.1016/j.disc.2007.12.020
复制
发表时间：
2008-12
期刊：
影响因子：
--
通讯作者：
Toru Araki
中科院分区：
文献类型：
--
作者：
Toru Araki
有向图 G 中的顶点 u 支配自身和所有顶点 v，使得 (u,v) 是 G 的弧，类似地，u 支配自身和所有顶点 w，使得 (w,u) 是 G 的弧。如果 G 的每个顶点都被 D 中的顶点支配并且被 D 中的顶点支配，则 G 的顶点集 D 是 G 的孪生支配集。 在本文中，我们介绍了有向图中的 k 元组孪生支配。如果 G 的每个顶点都被 D 中至少 k 个顶点支配并且被 D 中至少 k 个顶点支配，则 G 的顶点集 D 是 k 元孪生支配集。我们考虑 de Bruijn 有向图中的 k 元孪生支配问题，并给出在这些有向图中构造最小 k 元孪生支配集的构造方法。
A vertex u in a digraph G out-dominates itself and all vertices v such that (u,v) is an arc of G, similarly, u in-dominates both itself and all vertices w such that (w,u) is an arc of G. A set D of vertices of G is a twin dominating set of G if every vertex of G is out-dominated by a vertex of D and in-dominated by a vertex in D. In this paper, we introduce the k-tuple twin domination in directed graphs. A set D of vertices of G is a k-tuple twin dominating set if every vertex of G is out-dominated by at least k vertices in D and in-dominated by at least k vertices in D. We consider the problem of the k-tuple twin domination in de Bruijn and Kautz digraphs, and give construction methods for constructing minimum k-tuple twin dominating sets in these digraphs.