On VLSI Decompositions for-ary de Bruijn Graphs (Extended Abstract)
Tatsuhiro Yamada, H. Kawakita, T. Nishiyama, S. Ueno · 2005
A VLSI decomposition of a graph G is a collection of isomorphic vertex-disjoint subgraphs (called building blocks) of G which together span G. The efficiency of a VLSI decomposition is the fraction of the edges of G which are present in the subgraphs. The paper gives a necessary condition and a sufficient condition for a graph to be a building block for d-ary de Bruijn graphs. We also show building blocks for d-ary de Bruijn graphs with asymptotically optimal efficiency. Furthermore, we list the most efficient universal d-ary de Bruijn building blocks we know of.