Cores of cubelike graphs

A graph is cubelike if it is a Cayley graph for some elementary abelian 2-group Z₂ ⁿ. The core of a graph is its smallest subgraph to which it admits a homomorphism. More than ten years ago, Nešetřil and Šámal (2008) asked whether the core of a cubelike graph is cubelike, but since then very little progress has been made towards resolving the question. Here we investigate the structure of the core of a cubelike graph, deducing a variety of structural, spectral and group-theoretical properties that the core ”inherits” from the host cubelike graph. These properties constrain the structure of the core quite severely — even if the core of a cubelike graph is not actually cubelike, it must bear a very close resemblance to a cubelike graph. Moreover we prove the much stronger result that not only are these properties inherited by the core of a cubelike graph, but also by the orbital graphs of the core. Even though the core and its orbital graphs look very much like cubelike graphs, we are unable to show that this is sufficient to characterize cubelike graphs. However, our results are strong enough to eliminate all non-cubelike graphs on up to 32 vertices as potential cores of cubelike graphs (of any size). Thus, if one exists at all, a cubelike graph with a non-cubelike core has at least 128 vertices and its core has at least 64 vertices.