Operations Research Transactions >
2016 , Vol. 20 >Issue 3: 99 - 106
DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2016.03.011
Twin domination in generalized de Bruijn and Kautz digraphs
Received date: 2015-11-13
Online published: 2016-09-15
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\in V(G)\setminus T, there exist u, w\in T (possibly u=w) such that arcs (u,v),(v,w)\in A(G). The twin domination number \gamma^{*}(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 G_B(n,d) and generalized Kautz digraphs G_K(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.
DONG Yanxia, ZHANG Guang, SHAN Erfang . Twin domination in generalized de Bruijn and Kautz digraphs[J]. Operations Research Transactions, 2016 , 20(3) : 99 -106 . DOI: 10.15960/j.cnki.issn.1007-6093.2016.03.011
/
| 〈 |
|
〉 |