Cores of strongly regular graphs

Importance: High ✭✭✭
Recomm. for undergrads: no
Posted by: mdevos
on: June 16th, 2008

\begin{question} Does every \Def{strongly regular graph} have either itself or a complete graph as a \Def[core]{core (graph theory)}? \end{question}

If true, this curious question indicates a very interesting property of strongly regular graphs. While on the surface, there would appear to be no particular reason for it to hold, it has already been verified for a number of interesting classes of graphs. Cameron and Kazanidis [CK] showed that it holds for rank-3 graphs, while Godsil and Royle [GR] have showed that it holds for point graphs of generalized quadrangles, block graphs of Steiner systems and orthogonal arrays with sufficiently many points, and for all strongly regular graphs on at most 36 vertices.


*[CK] P. J. Cameron and P. A. Kazanidis, Cores of symmetric graphs, J. Australian Math. Soc., to appear.

[GR] C. Godsil and G.F. Royle, \href[Cores of Geometric Graphs]{}

* indicates original appearance(s) of problem.


I believe you mean "Godsil and Royle", not "Gordon and Royle".

Comment viewing options

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