中文

Operations Research Transactions >

2021 , Vol. 25 >Issue 2: 127 - 134

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2021.02.010

k-tuple domination in generalized de Bruijn digraphs

Expand
  • 1. School of Statistics and Information, Shanghai University of International Business and Economics, Shanghai 201620, China
    2. School of Management, University of Shanghai for Science and Technology, Shanghai 200093, China

Received date: 2020-11-13

  Online published: 2021-05-06

Fold

Abstract

Let $G=(V, A)$ be a digraph with vertex set $V$ and arc set $A$. A set $D_{k}$ of vertices of $G$ is a $k$-tuple dominating set of $G$ if for every vertex $v\in V(G)\setminus D_{k}$, there exists $u_{i}\in D_{k}$ (possibly some vertex $u_{i}=v$) such that arcs $(u_{i},v)\in A(G)$ for $1\leq i\leq k$. The $k$-tuple domination number $\gamma_{\times k}(G)$ of $G$ is the cardinality of a minimum $k$-tuple dominating set of $G$. In this paper we present a new upper bound on the $k$-tuple domination number of generalized de Bruijn digraphs $G_B(n,d)$. Furthermore, the method of constructing a $k$-tuple dominating set of generalized de Bruijn digraph is given. %which improves the known upper bound in previous literature. For special generalized de Bruijn digraphs, we further improve the bounds on $k$-tuple domination number by directly constructing $k$-tuple dominating sets.

Key words： generalized de Bruijn digraphs; dominating set; k-tuple dominating set

Cite this article

Yanxia DONG, Tao XUE, Guang ZHANG . k-tuple domination in generalized de Bruijn digraphs[J]. Operations Research Transactions, 2021 , 25(2) : 127 -134 . DOI: 10.15960/j.cnki.issn.1007-6093.2021.02.010

References

1 Haynes T W , Hedetniemi S T , Slater P J . Fundamentals of Domination in Graphs[M]. New York: Marcel Dekker, 1998.
2 Harary F , Haynes T W . Double domination in graphs[J]. Ars Combinatoria, 2000, 55, 201- 213.
3 Chang G J . The upper bound on k-tuple domination numbers of graphs[J]. European Journal of Combinatorics, 2008, 29, 1333- 1336.
4 Gagarin A , Zverovich V E . A generalised upper bound for the k-tuple domination number[J]. Discrete Mathematics, 2008, 308, 880- 885.
5 Xu G J , Kang L Y , Shan E F , et al. Proof of a conjecture on k-tuple domination in graphs[J]. Applied Mathematics Letters, 2008, 21, 287- 290.
6 Ghoshal J, Laskar R, Pillone D. Topics on Domination in Directed Graphs[M]//Domination in Graphs: Advanced Topics. New York: Marcel Dekker Inc, 1998, 401-437.
7 Araki T . On the k-tuple domination of de Bruijn and Kautz digraphs[J]. Information Processing Letters, 2007, 104, 86- 90.
8 Wu L Y , Shan E F , Liu Z R . On the k-tuple domination of generalized de Brujin and Kautz digraphs[J]. Information Sciences, 2010, 180 (22): 4430- 4435.
9 Imase M , Itoh M . Design minimize diameter on building block network[J]. IEEE Transactions on Computers, 1981, 30 (6): 439- 442.
10 Shibata Y , Shirahata M , Osawa S . Counting closed walks in generalized de Bruijn graphs[J]. Information Processing Letters, 1994, 49, 135- 138.
11 Kikuchi Y , Shibata Y . On the domination numbers of generalized de Bruijn digraphs and generalized Kautz digraphs[J]. Information Processing Letters, 2003, 86 (2): 79- 85.
12 Shan E F , Cheng T C E , Kang L Y . Absorbant of generalized de Bruijn digraphs[J]. Information Processing Letters, 2007, 105 (1): 6- 11.
13 Shan E F , Dong Y X , Cheng Y K . The twin domination number in generalized de Bruijn digraphs[J]. Information Processing Letters, 2009, 109 (15): 856- 860.
14 Wang Y L . Efficient twin domination in generalized de Bruijn digraphs[J]. Discrete Mathematics, 2015, 338 (3): 36- 40.
15 Dong Y X , Shan E F , Kang L Y . Constructing the minimum dominating sets of generalized de Bruijn digraphs[J]. Discrete Mathematics, 2015, 338 (8): 1501- 1508.
16 Pan C D , Pan C B . Elementary Number Theory[M]. Beijing: Beijing University Press, 2004.
Options
Outlines

/

〈 〉