2
$\begingroup$

I do not know if I miss something in the definition of a hyper-cube, but as far as I understand, Hyper-cube graphs have 2^n vertices and if written in binary form, "one-bit difference" strings of numbers are linked with an edge.

From this definition, De Bruijn graph does not look like it is a hyper-cube, because 000 and 010 for example, are not adjacent.

Improve this question
$\endgroup$
3
  • $\begingroup$ Your definition of a hypercube is correct. The De Bruijn graph I have in my mind is a directed graph; were you thinking of something else? $\endgroup$ – Juho Jul 2 '18 at 11:03
  • 2
    $\begingroup$ The correct question is whether the de Bruijn graph is isomorphic to a hypercube. It probably isn't, except perhaps for some exceptional parameter settings. $\endgroup$ – Yuval Filmus Jul 2 '18 at 11:17
  • $\begingroup$ All I know is in my class De Bruijn is defined as a hyper-cube, and it does not look like one according to the definition. An example in my mind is here: en.wikipedia.org/wiki/De_Bruijn_graph#/media/… $\endgroup$ – Ninja Bug Jul 2 '18 at 11:31
7
$\begingroup$

No. I was writing an answer based on vertex and edge counts, but then I realised that there's a simpler argument: the de Bruijn graph of strings of length $n$ over an alphabet of $m$ symbols has $m$ self-loops, whereas a hypercube has none.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.