Cores of vertex transitive graphs

MaRDI QIDQ1953537zbMATH OpenFDO

Authors David Roberson

Publication date 7 June 2013

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1302.4470, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i2p45

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

core of a graphgraph homomorphismsvertex minimal subgraphvertex transitive graphs

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: A core of a graph X is a vertex minimal subgraph to which X admits a homomorphism. Hahn and Tardif have shown that for vertex transitive graphs, the size of the core must divide the size of the graph. This motivates the following question: when can the vertex set of a vertex transitive graph be partitioned into sets each of which induce a copy of its core? We show that normal Cayley graphs and vertex transitive graphs with cores half their size always admit such partitions. We also show that the vertex sets of vertex transitive graphs with cores less than half their size do not, in general, have such partitions.

Recommendations

• CORES OF SYMMETRIC GRAPHS
• scientific article; zbMATH DE number 434696
• Cores of cubelike graphs
• Cores of non-normal Cayley graphs of order ${p^2}$
• The core of a graph

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?)
• Vertex-transitive graphs

Cited in

(9)

• Cores of cubelike graphs
• \(\lambda\)-core distance partitions
• Cores of imprimitive symmetric graphs of order a product of two distinct primes
• scientific article; zbMATH DE number 434696 (Why is no real title available?)
• On Minkowski space and finite geometry
• CORES OF SYMMETRIC GRAPHS
• Cores of non-normal Cayley graphs of order ${p^2}$
• The core of a complementary prism
• The core of a vertex-transitive complementary prism

This page was built for publication: Cores of vertex transitive graphs

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