SEMINAR: Groups and Combinatorics Seminar: Cores of cubelike graphs

Time and place: 15:00 Friday 1 May in Weatherburn LT.

Speaker: David Roberson (Nanyang Technological University)

Title: Cores of cubelike graphs.

Abstract: A graph is said to be cubelike if it is a Cayley graph for some power of the group of order two. The core of a graph is its smallest subgraph to which it admits a homomorphism. In this talk we consider the following open question: Is the core of a cubelike graph cubelike? We will discuss the previously known results on this problem before proving the following:

Theorem: If X is a core of a cubelike graph and has degree k, then X has at most 2^(k-1) vertices or is K_2. Furthermore, if k is at least 2 and the above bound is met, then k is odd and X is the folded cube of order k.

This result is as expected if the answer to the above question is "yes", and thus it provides some evidence that this is in fact the case. We will also discuss some properties that would be required of a minimal counterexample to the conjecture if time permits.