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

graph homomorphismsvertex transitive graphscore of a graphvertex minimal subgraph

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

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)