The k-Dimensional Cube is k-Representable
Broere, Bas, Zantema, Hans · Radboud Repository (Radboud University) · 2019
A graph is called $k$-representable if there exists a word $\fwo$ over the nodes of the graph, each node occurring exactly $k$ times, such that there is an edge between two nodes~$\fle,\sle$ if and only after removing all letters distinct from $\fle,\sle$, from $\fwo$, a word remains in which~$\fle,\sle$ alternate. We prove that if $G$ is $k$-representable for $k>1$, then the Cartesian product of $G$ and the complete graph on $n$ nodes is $(k+n-1)$-representable. As a direct consequence, the $k$-dimensional cube is $k$-representable for every $k \geq 1$. Our main technique consists of exploring occurrence-based functions that replace every $i$th occurrence of a symbol $\fle$ in a word $\fwo$ by a string $h(\fle,i)$. The representing word we construct to achieve our main theorem is purely composed from concatenation and occurrence-based functions.