Cores of strongly regular graphs

High ★★★ Graph Theory » Algebraic Graph Theory

Authors: Cameron, Peter J., Kazanidis, Priscila A.— posted by mdevos on 2008-06-16

Status solved high confidence

David E. Roberson proved the Cameron-Kazanidis conjecture in 2019, showing that every primitive strongly regular graph is either a core or has a complete core. More precisely, he proved that any homomorphism between primitive strongly regular graphs with the same parameters is either an isomorphism or a coloring (homomorphism onto a complete subgraph), so the endomorphisms of a primitive strongly regular graph are exactly its automorphisms and its optimal colorings.

Cited literature (2)

proof Homomorphisms of strongly regular graphs (2019)

David E. Roberson · Algebraic Combinatorics · arXiv:1610.10002 · doi:10.5802/alco.50

Proves the Cameron-Kazanidis conjecture: every primitive strongly regular graph is either a core or has a complete core, by showing that endomorphisms of a primitive SRG are automorphisms or colorings.
partial On cores of distance-regular graphs (2025)

Annemarie Geertsema, Chris Godsil, Krystal Guo · arXiv preprint · arXiv:2504.00129

Extends Roberson's homomorphism-matrix approach to distance-regular graphs, recovering the Cameron-Kazanidis result for diameter 2 and proving that retractions of certain primitive distance-regular graphs onto a diameter-d subgraph must be automorphisms.

Reviewer notes. The Cameron-Kazanidis conjecture (problem posted 2008) was settled in the affirmative by Roberson (Algebraic Combinatorics 2, 2019, pp. 481-497; arXiv:1610.10002). The result is for primitive strongly regular graphs; non-primitive (i.e. disjoint unions of complete graphs or their complements) are trivial cases. The Geertsema-Godsil-Guo 2025 preprint extends the technique to distance-regular graphs.

Auto-reviewed 2026-05-08 with claude-sonnet (subagent) (web search enabled).

Question. Does every strongly regular graph have either itself or a complete graph as a core ?

Keywords: core · strongly regular

Discussion

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.

Bibliography

★ [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, Cores of Geometric Graphs Cores of Geometric Graphs