In my new Wikipedia article on the queue number of graphs, the binary de Bruijn graphs form an important family of examples. These are 4-regular graphs with one vertex for every n-bit binary string, and with an edge from every string of the form 0s or 1s to s0 or s1. I posted about them here several years ago, with the following drawing, which can be interpreted as a 2-queue drawing with one queue for the edges that wrap around the left side and another for the edges that wrap around the right.

Order-3 binary de Bruijn graph

Graph minors also showed up in the article, and it occurred to me to wonder: do de Bruijn graphs belong to any minor-closed graph families? The answer should be no, because they're too highly connected, but can we quantify this? One way would be to determine the Hadwiger number of the de Bruijn graphs, i.e., the size of their largest clique minors. As long as this is not bounded by a constant, the de Bruijn graphs do not belong to any nontrivial minor-closed family. And in fact, that turns out to be true: the Hadwiger number is somewhere near the square root of the number of vertices.

One direction is easy: an \( n \)-vertex de Bruijn graph has \( 2n \) edges, and a \( k \)-vertex clique minor needs at least \( k(k-1)/2 \) edges, so \( k \) has to be at most approximately \( 2\sqrt{n} \).

In the other direction, it's possible to exhibit an explicit clique minor of size nearly the square root of \( n \) in any de Bruijn graph. To do so, I need three ingredients:

(1) A representative vertex in the de Bruijn graph for each clique vertex,

(2) A path in the de Bruijn graph between any two representative vertices (not necessarily disjoint from the other paths), and

(3) A mapping from the vertices within these paths to representative vertices, such that each path can be split into two segments that are mapped to the two endpoints of the path.

With these ingredients, the minor itself can be formed by throwing away non-path vertices and contracting path edges between pairs of vertices that are mapped to the same endpoint as each other. (Every clique minor of any graph can be represented in this way.)

So here are the representative vertices: for order-\( k \) de Bruijn graphs (with \( n=2^k \) vertices) they are the binary strings of the form \( 1x1y1y \), where \( x \) is a string of about \( \log_2 k \) consecutive 0's and \( y \) is a string of length \( (k-\mathrm{len}(x) - 3)/2 \) that doesn't contain \( x \) as a substring. The \( y \) part of this is what distinguishes this representative vertex from all the other ones, and we will look for this string to determine how to map path vertices to representative vertices. The \( x \) part of the string carries no useful identifying information, but instead will allow us to find \( y \) even when the string has been shifted and mangled in the process of finding a path between two representative vertices. With this choice of the length of \( x \), a constant fraction of the strings that are the right length to be \( y \) are valid (don't contain \( x \) as a substring). The number of valid \( y \)'s, and therefore the size of the clique minor that we find, is proportional to the square root of \( n/\log n \).

To find a path from one representative vertex to another, we simply follow edges that shift the bitstring left by one position, shifting in the bits of the second representative vertex as we shift out the bits of the first. This actually gives two paths between each two representative vertices (one in each direction) but that isn't a problem; just pick one of the two.

In order to define the mapping from path vertices to representative vertices, it's convenient to think of a bitstring (vertex of the de Bruijn graph) as having its left end wrapped around and glued to the right end to form a single cyclic sequence of bits. As we follow the path, the string \( x \) of consecutive 0's will rotate from the left side of the string to the right and then back to the left, but will always be uniquely identifiable as the only string of consecutive 0's of the correct length in this cyclic sequence. From the position of \( x \), in any path vertex, we can identify two substrings in the cyclic sequence, in the correct positions relative to \( x \) to be the \( y \)'s of a representative vertex. For the first half of the path, one of these two \( y \) substrings will be equal to the \( y \) of the starting vertex of the path, and the second will be arbitrary (some mix of the two path endpoints). For the second half of the path, the pattern is reversed: the other one of the two \( y \) substrings will be equal to the \( y \) of the ending vertex of the path, and the other one will be a mix. But we can tell which of these two situations is the case by looking at the position of the consecutive 0's. So we map each path vertex to the representative vertex for one of its two \( y \) substrings, the one that isn't mixed up.

So which of \( \sqrt{n} \) (the edge-counting upper bound) and \( \sqrt{n/\log n} \) (the explicit construction of a clique minor) is closer to the truth? I'm not sure. On the one hand, if you have representative vertices \( k \) units apart from each other (as seems necessary, up to constant factors) with disjoint paths between them in the clique minor, then comparing the total number of edges in these paths with the total number of edges in the complete minor would show that the \( \sqrt{n/\log n} \) bound is tight. On the other hand, in the construction above, the paths are not disjoint, and they can't be because the representative vertex doesn't have high degree. But I don't know how to define the mapping from paths from representative vertices without, seemingly, wasting bits on the \( x \) strings which are used only as markers to determine where in the path each vertex is.

(G+)