A New Property of Binary Undirected de Bruijn Graphs

Abstract

The authors obtain a new property of the n-dimensional binary undirected de Bruijn graph UB(n) for n ≥ 4, namely, there is a vertex x such that for any other vertex y there exist at least two internally disjoint paths of length at most n - 1 between x and y in UB(n). The result means that the (n - 1, 2)-dominating number of UB(n) is equal to one if n ≥ 4.

Keywords

de Bruijn graph / Wide-diameter / Length of path / Dominating number / 05C40 / 68M10 / 68R10 / O157.5 / O157.9

References

[1] Bermond, J. & Peyrat, C., de Bruijn and Kautz networks: a competitor for the hypercube? Proc. the first European Workshop on Hypercube and Distributed Computers, in Hypercube and Distributed Computers (eds. F. Andre and J. P. Verjus), North-Holland, Amsterdam, 1989, 179-294.

[2] Garey, M. R. & Johnson, D. S., Computer and intractability: a guide to the theory of NP-completeness, Freeman, New York, 1979.

[3] Li Q, Sotteau D, Xu J M. 2-diameter of de Bruijn graphs. Networks, 1996, 28: 7-14

[4] Li H, Xu J M. (d, m)-dominating numbers of m-connected graphs, Rapports de Recherche. LRI, URA410 du CNRS Unversite de Paris-Sud, 1997, 1130: 1-17

[5] Pradhan D K. Faut tolerant VLSI architectures based on de Bruijn graphs (Galileo in the mid nineties). Reliability of Computer and Communication Networks, DIMACS Series in Disc. Math. Theor. Comput. Sci., 1991, 5: 183-196

[6] Wang, Z. X., Algebra and coding (in Chinese), Academic Press, Beijing, 1976.