Cores of strongly regular and other highly structured graphs

Chris Godsil and Gordon Royle (speaker)


One of the fundamental concepts in the theory of graph homomorphisms is that of a core, i.e.
a graph that has no homomorphisms to any of its proper subgraphs. It is easy to see that every
graph X contains a unique (up to isomorphism) subgraph Y with the properties that Y is both a
homomorphic image of X and is also a core; this subgraph is known as the core of X.  In general
it is hard both theoretically and practically to identify the core of a graph and there are few families
of graphs for which the cores are known.


In this talk, I will discuss the problem of determining the core for certain families of highly structured
graphs such as strongly regular graphs and vertex transitive graphs. In some cases the cores can be
determined completely while in other cases the problem reduces to interesting unsolved problems in
finite geometry or graph colouring.


This talk is very much a description of work-in-progress and will contain as many questions as answers.
All "homomorphism" terminology will be defined from scratch and so the talk will be accessible to anyone
familiar with basic graph theory.