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.

Keywords

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)

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg