Home » Subject » Graph Theory » Coloring » Homomorphisms

Cores of Cayley graphs

Importance: Medium ✭✭
Author(s): Samal, Robert
Subject: Graph Theory
» Coloring
» » Homomorphisms
Keywords: Cayley graph
core
Recomm. for undergrads: no
Posted by: Robert Samal
on: March 6th, 2007
Conjecture   Let $ M $ be an abelian group. Is the core of a Cayley graph (on some power of $ M $) a Cayley graph (on some power of $ M $)?

Even the case $ M=\mathbb{Z}_2 $ is open. In this case, Cayley graphs on some power of $ \mathbb{Z}_2 $ are called cube-like graphs, they have been introduced by Lov\'asz as an example of graphs, for which every eigenvalue is an integer.

So, in this case we ask, whether a core of each cube-like graph is a cube-like graph.

add new comment

Who first conjectured this?

On February 29th, 2012 Anonymous says:

Who first conjectured that the core of a cubelike graph is cubelike?

reply

Question needs refining...

On February 22nd, 2008 Gordon Royle says:

As stated, the conjecture is false in an uninteresting way ... it is possible for a Cayley graph of Z_15 have a 5-cycle as a core.... So if we take M = Z_15 then the result is false.

Perhaps the question should either (a) be restricted to elementary abelian groups or (b) have the conclusion being that the core of a Cayley graph on M must be a Cayley graph on N where N is a (group) homomorphic image of M.

Gordon Royle http://people.csse.uwa.edu.au/gordon

reply

Re: Question needs refining...

On March 1st, 2008 Robert Samal says:

That is true. I was mainly thinking about $ M={\mathbb Z}_p $ (for a prime $ p $). However, your suggestion (b) looks sensible as well.

Thanks for your comment!

Robert Samal

reply

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.