Cores of cubelike graphs

DOI10.1016/J.EJC.2020.103092MaRDI QIDQ2178667zbMATH OpenOpenAlexFDO

Authors L. Mančinska, Irene Pivotto, David Roberson, Gordon Royle

Publication date 11 May 2020

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1808.02051

zbMATH Keywords

Cayley graph

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Abstract: A graph is $extitcubelike$ if it is a Cayley graph for some elementary abelian $2$-group $mathbb{Z}_2^n$. The core of a graph is its smallest subgraph to which it admits a homomorphism. More than ten years ago, Nev{s}etv{r}il and v{S}'amal (On tension-continuous mappings. $extitEuropeanJ.Combin.,$ 29(4):1025--1054, 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 characterise cubelike graphs. However, our results are strong enough to eliminate all non-cubelike vertex-transitive 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.

Recommendations

• Cores of vertex transitive graphs
• CORES OF SYMMETRIC GRAPHS
• scientific article; zbMATH DE number 434696
• The core of a graph
• Cores of geometric graphs

Cites work

• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 1054727 (Why is no real title available?)
• Homomorphisms of binary Cayley graphs
• On normal Cayley graphs and hom-idempotent graphs
• On tension-continuous mappings
• On the chromatic number of cube-like graphs
• Spectra of graphs
• Spectra of graphs with transitive groups
• The Transitive Permutation Groups of Degree 32

Cited in

(6)

• The core of a graph
• Cores of vertex transitive graphs
• The core of a complementary prism
• scientific article; zbMATH DE number 434696 (Why is no real title available?)
• CORES OF SYMMETRIC GRAPHS
• Cores of geometric graphs

Describes a project that uses

Uses Software

• Digraphs

This page was built for publication: Cores of cubelike graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2178667)