Cores of cubelike graphs

Research output: Contribution to journal › Journal article › Research › peer-review

Standard

Cores of cubelike graphs. / Mančinska, Laura; Pivotto, Irene; Roberson, David E.; Royle, Gordon F.

In: European Journal of Combinatorics, Vol. 87, 103092, 2020.

Research output: Contribution to journal › Journal article › Research › peer-review

Harvard

Mančinska, L, Pivotto, I, Roberson, DE & Royle, GF 2020, 'Cores of cubelike graphs', European Journal of Combinatorics, vol. 87, 103092. https://doi.org/10.1016/j.ejc.2020.103092

APA

Mančinska, L., Pivotto, I., Roberson, D. E., & Royle, G. F. (2020). Cores of cubelike graphs. European Journal of Combinatorics, 87, [103092]. https://doi.org/10.1016/j.ejc.2020.103092

Vancouver

Mančinska L, Pivotto I, Roberson DE, Royle GF. Cores of cubelike graphs. European Journal of Combinatorics. 2020;87. 103092. https://doi.org/10.1016/j.ejc.2020.103092

Author

Mančinska, Laura ; Pivotto, Irene ; Roberson, David E. ; Royle, Gordon F. / Cores of cubelike graphs. In: European Journal of Combinatorics. 2020 ; Vol. 87.

Bibtex

@article{c366f4d422f048ae85e3e42eac4ec9bb,
title = "Cores of cubelike graphs",
abstract = "A graph is cubelike if it is a Cayley graph for some elementary abelian 2-group Z2 n. The core of a graph is its smallest subgraph to which it admits a homomorphism. More than ten years ago, Ne{\v s}et{\v r}il and {\v S}{\'a}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.",
author = "Laura Man{\v c}inska and Irene Pivotto and Roberson, {David E.} and Royle, {Gordon F.}",
year = "2020",
doi = "10.1016/j.ejc.2020.103092",
language = "English",
volume = "87",
journal = "European Journal of Combinatorics",
issn = "0195-6698",
publisher = "Academic Press",

}

RIS

TY - JOUR

T1 - Cores of cubelike graphs

AU - Mančinska, Laura

AU - Pivotto, Irene

AU - Roberson, David E.

AU - Royle, Gordon F.

PY - 2020

Y1 - 2020

N2 - A graph is cubelike if it is a Cayley graph for some elementary abelian 2-group Z2 n. 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.

AB - A graph is cubelike if it is a Cayley graph for some elementary abelian 2-group Z2 n. 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.

UR - http://www.scopus.com/inward/record.url?scp=85082437640&partnerID=8YFLogxK

U2 - 10.1016/j.ejc.2020.103092

DO - 10.1016/j.ejc.2020.103092

M3 - Journal article

AN - SCOPUS:85082437640

VL - 87

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

SN - 0195-6698

M1 - 103092

ER -

ID: 240640483