Embedding of the hypercube into the generalized De Bruijn graph (UGB(2^n-1,2^n ) - Regmi, Regina (2001)
The generalized de Bruijn graph UGb(2 to the n-1, 2 to the n) having 2 to the n vertices labeled from 0,1,...,2 to the n -1 is a regular graph with vertex degree 2 to the n-1 and diameter 2. For any positive integer n>_ 2. It can be divided into two equal halves, H1 and H2, such that H1 contains vertices [0,2 to n-1 -1] and H2 contains vertices [2 to n -1 power, 2 to n -1]. Two vertices A and B are adjacent if and only if they are opposite parity from the same half, or they are of same parity from different halves. The generalized de Bruijn graph has a promising feature as a network topology. This is because of its high connectivity and small diameter. In this research paper, we will study the generalized de Bruijn graph UGb(2 to the n-1, 2 to the n). We will also show some special properties of generalized de Bruijn graph UGb(2 to n-1, to 2 to n) such as, the symmetry between H1 and H2, automorphism, and recursive mapping. The embedding of hypercube Qn indirectly shows the embedding of all network topologies, which can be embedded into Qn, can also be embedded into the generalized de Bruijn graph UGb(2 to n-1, 2 to the n). Problems solvable by algorithms that can run on Qn will therefore also run on UGb(2 to the n-1, 2 to the n), with potential improvements in running time. Its low diameter (2) makes UGb(2 to n-1, 2 to n) a much more powerful graph than Qn in terms of data exchange, routing, and other communication intensive problems.