4 problems

For $r\geq 3$, let $BF(r)$ be the $r$-dimensional butterfly network, whose vertices are pairs $[s,j]$, where $s$ is an $r$-bit binary string and $j\in\{0,1,\ldots,r\}$. Let…

Let $S$ be a set of transpositions generating $S_n$, with $n\ge 3$, and let $T(S)$ be the transposition graph of $S$. Write $\Cay(S_n,S)$ for the Cayley graph generated by $S$,…

Cube-connected-cycles non-embeddability conjecture. For the tested values $n=3,4,5$, $CCC_n$ is not $(n+1)$-tr.embeddable.

De Bruijn–Kautz non-embeddability conjecture. (i) All $Br(m,n)$ with $(m,n)\neq(2,2)$ are not $2$-tr.embeddable. (ii) All $Ka(m,n)$ with $m\geq 3$ are not $2$-tr.embeddable.