广义de Bruijn和Kautz有向图的双向控制集

Twin domination in generalized de Bruijn and Kautz digraphs

设G=（V,A）是一个有向图,其中V和A分别表示有向图G的点集和弧集.对集合TV（G）,如果对于任意点v∈V（G）／T,都存在点u,w∈T（u,w可能是同一点）使得（u,v）,（v,w）∈A（G）,则称T是G的一个双向控制集.有向图G的双向控制数γ-＊（G）是G的最小双向控制集所含点的数目.提出了广义de Bruijn和Kautz有向图的双向控制数的新上界,改进了以前文献中提出的相关结论.此外,对某些特殊的广义de Bruijn和Kautz有向图,通过构造其双向控制集,进一步改进了它们双向控制数的上、下界.

Let G = （V, A） be a digraph with vertex set V and arc set A. A set T of vertices of G is a twin dominating set of G if for every vertex v∈V（G）／T, there exist u, w E T （possibly u = w） such that arcs （u, v）, （v, w） E A（G）. The twin domination number γ-＊（G） of G is the cardinality of a minimum twin dominating set of G. In this paper we present a new upper bound on the twin domination number of generalized de Bruijn digraphs Gs（n, d） and generalized Kautz digraphs Gk（n, d）, which improves the known upper bound in previous literature. For special generalized de Bruijn and Kautz digraphs, we further improve the bounds on twin domination number by directly constructing their twin dominating sets.