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.

$\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, 2018 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$ Jul 2, 2018 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, 2018 at 11:31

1 Answer 1

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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