Cores of cubelike graphs

Laura Mančinska, Irene Pivotto, David E. Roberson, Gordon F. Royle

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

A graph is cubelike if it is a Cayley graph for some elementary abelian 2-group Z2n. 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.
Original languageEnglish
Article number103092
JournalEuropean Journal of Combinatorics
Volume87
Number of pages16
ISSN0195-6698
DOIs
Publication statusPublished - 2020

Cite this