Distance domination of generalized de Bruijn and Kautz digraphs

Abstract

Let G = (V,A) be a digraph and k\ge \mathrm{1} an integer. For u, v ∈ V, we say that the vertex u distance k-dominate v if the distance from u to v at most k. A set D of vertices in G is a distance k-dominating set if each vertex of V \ D is distance k-dominated by some vertex of D. The distance k-domination number of G, denoted by γk(G), is the minimum cardinality of a distance k-dominating set of G. Generalized de Bruijn digraphs G_B(n, d) and generalized Kautz digraphs G_K(n, d) are good candidates for interconnection networks. Denote {{\displaystyle \Delta }}_k:={({\displaystyle {\sum }_{j=\mathrm{0}}^k{d}^j})}^{-\mathrm{1}}. F. Tian and J. Xu showed that \lceil n{{\displaystyle \Delta }}_k\rceil \le {{\displaystyle \gamma }}_k({{\displaystyle G}}_B(n,d))\le \lceil n/d^k\rceil and \lceil n{{\displaystyle \Delta }}_k\rceil \le {{\displaystyle \gamma }}_k({{\displaystyle G}}_K(n,d))\le \lceil n/d^k\rceil. In this paper, we prove that every generalized de Bruijn digraph G_B(n, d) has the distance kdomination number \lceil n{{\displaystyle \Delta }}_k\rceil or \lceil n{{\displaystyle \Delta }}_k\rceil +\mathrm{1}, and the distance k-domination number of every generalized Kautz digraph G_K(n, d) bounded above by \lceil n/d^{k-\mathrm{1}}+d^k\rceil. Additionally, we present various sufficient conditions for {{\displaystyle \gamma }}_k({{\displaystyle G}}_B(n,d))=\lceil n{{\displaystyle \Delta }}_k\rceil and {{\displaystyle \gamma }}_k({{\displaystyle G}}_K(n,d))=\lceil n{{\displaystyle \Delta }}_k\rceil.

Key words： Combinatorial problems; dominating set; distance dominating set; generalized de Bruijn digraph; generalized Kautz digraph

References

1 Araki T. On the k-tuple domination in de Bruijn and Kautz digraphs. Inform Process Lett, 2007, 104: 86–90

2 Bermond J C, Peyrat C. De Bruijn and Kautz networks: a competitor for the hypercube? In: André F, Verjus J P, eds. Hypercube and Distributed Computers. North-Holland: Elsevier Science Publishers, 1989, 279–293

3 Caro Y, Henning M A. Directed domination in oriented graphs. Discrete Appl Math, 2012, 160: 1053–1063

4 Deng A, Wu Y K. De Bruijn digraphs and affine transformations. European J Combin, 2005, 26: 1191–1206

5 Dong Y X, Shan E F, Kang L Y. Constructing the minimum dominating sets of generalized de Bruijn digraphs. Discrete Math, 2015, 338: 1501–1508

6 Du D Z, Hsu D F, Hwang F K, Zhang X M. The Hamiltonian property of generalized de Bruijn digraphs. J Combin Theory Ser B, 1991, 52: 1–8

7 Ducoffe G. Hamiltonicity of large generalized de Bruijn cycles. Discrete Appl Math, 2013, 161: 2200–2204

8 Fischermann M, Volkmann L. Graphs having distance n-domination number half their order. Discrete Appl Math, 2002, 120: 97–107

9 Ghoshal J, Laskar R, Pillone D. Topics on domination in directed graphs, In: Haynes T W, Hedetniemi S T, Slater P J, eds. Domination in Graphs: Advanced Topics. New York: Marcel Dekker, 1998, 401–437

10 Hasunuma T, Shibata Y.Counting small cycles in generalized de Bruijn digraphs. Networks, 1997, 29: 39–47

11 Haynes T W, Hedetniemi S T, Slater P J. Fundamentals of Domination in Graphs.New York: Marcel Dekker, 1998

12 Hosseinabady M, Kakoee M R, Mathew J, Pradhan D K. Low latency and energy efficient scalable architecture for massive NoCs using generalized de Bruijn graph. IEEE Trans on Very Large Scale Integration Systems, 2011, 19: 1469–1480

13 Imase M, Itoh M. Design to minimize diameter on building-block networks. IEEE Trans Comput, 1981, C-30: 439–442

14 Imase M, Soneoka T, Okada K. Connectivity of regular directed graphs with small diameters. IEEE Trans Comput, 1985, 34: 267–273

15 Kikuchi Y, Shibata Y. On the domination numbers of generalized de Bruijn digraphs and generalized Kautz digraphs. Inform Process Lett, 2003, 86: 79–85

16 Li X, Zhang F. On the numbers of spanning trees and Eulerian tours in generalized de Bruijn graphs. Discrete Math, 1991, 94: 189–197

17 Lien M Y, Kuo J, Fu H L. On the decycling number of generalized Kautz digraphs. Inform Process Lett, 2015, 115: 209–211

18 Pan C D, Pan C B. Elementary Number Theory. 2nd ed.Beijing: Beijing Univ Press, 2004 (in Chinese)

19 Shan E F, Cheng T C E, Kang L Y. Absorbant of generalized de Bruijn digraphs. Inform Process Lett, 2007, 105: 6–11

20 Shan E F, Dong Y X. The k-tuple twin domination in generalized de Bruijn and Kautz networks. Comput Math Appl, 2012, 63: 222–227

21 Shan E F, Dong Y X, Cheng Y K. The twin domination number in generalized de Bruijn digraphs. Inform Process Lett, 2009, 109: 856–860

22 Shibata Y, Shirahata M, Osawa S. Counting closed walks in generalized de Bruijn graphs. Inform Process Lett, 1994, 49: 135–138

23 Slater P J. R-dominations in graphs. J Assoc Comput Mach, 1976, 23: 446–460

24 Sridharan N, Subramanian V S A, Elias M D. Bounds on the distance two-domination number of a graph. Graphs Combin, 2002, 18: 667–675

25 Tian F, Xu J. Distance domination numbers of generalized de Bruijn and Kautz digraphs. OR Trans, 2006, 10: 88–94

26 Wang Y L. Efficient twin domination in generalized de Bruijn digraphs. Discrete Math, 2015, 338: 36–40

27 Xu J M. Combinatorial Network Theory.Beijing: Science Press, 2007, 112–131 (in Chinese)