<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
Cores of Geometric Graphs
Chris Godsil1 and Gordon F. Royle2
1Department of Combinatorics and Optimization, University of Waterloo, 200 University Avenue West, Waterloo, Ontario, N2L 3G1, Canada
2School of Mathematics and Statistics, University of Western Australia, 35 Stirling Highway Crawley, Perth 6009, Western Australia, Australia
Annals of Combinatorics 15 (2) pp.267-276 April, 2011
AMS Subject Classification: 05C15; 51E14
Cameron and Kazanidis have recently shown that rank-three graphs are either cores or have complete cores, and they asked whether this holds for all strongly regular graphs. We prove that this is true for the point graphs and line graphs of generalized quadrangles and that when the number of points is sufficiently large, it is also true for the block graphs of Steiner systems and orthogonal arrays.
Keywords: graph homomorphism, core, strongly regular graph, partial geometry


1. Beth, T., Jungnickel, D., Lenz, H.: Design Theory. Bibliographisches Institut, Mannheim (1985)

2. Blokhuis, A., Brouwer, A.E.: Locally 4-by-4 grid graphs. J. Graph Theory 13(2), 229–244 (1989)

3. Bose, R.C.: Strongly regular graphs, partial geometries and partially balanced designs. Pacific J. Math. 13, 389–419 (1963)

4. Brouwer, A.E., Cohen, A.M., Neumaier, A.: Distance-Regular Graphs. Springer-Verlag, Berlin (1989)

5. Brouwer, A.E., van Lint, J.H.: Strongly regular graphs and partial geometries. In: Enumeration and Design (Waterloo, Ont., 1982), pp. 85–122. Academic Press, Toronto (1984)

6. Cameron, P.J., Kazanidis, P.A.: Cores of symmetric graphs. J. Aust. Math. Soc. 85(2), 145–154 (2008)

7. Godsil, C., Royle, G.: Algebraic Graph Theory. Springer-Verlag, New York (2001)

8. Hahn, G., Tardif, C.: Graph homomorphisms: structure and symmetry. In: Graph Symmetry, pp. 107–166. Kluwer Acad. Publ., Dordrecht (1997)

9. Hell, P., Neˇsetˇril, J.: Graphs and Homomorphisms. Oxford University Press, Oxford (2004)

10. Mathon, R.A., Phelps, K.T., Rosa, A.: Small Steiner triple systems and their properties. Ars Combin. 15, 3–110 (1983)

11. Neumaier, A.: Strongly regular graphs with smallest eigenvalue −m. Arch. Math. (Basel) 33(4), 392–400 (1979/80)

12. Payne, S.E., Thas, J.A.: Finite Generalized Quadrangles. Boston, MA (1984)

13. Thas, J.A.: Ovoids, spreads and m-systems of finite classical polar spaces. In: Surveys in Combinatorics, pp. 241–267. Cambridge University Press, Cambridge (2001)

14. Thas, J.A.: Partial geometries. In: Colbourn, C.J., Dinitz, J.H., (eds.) Handbook of Combinatorial Designs, pp. 557–561. Chapman & Hall/CRC, Boca Raton, FL (2006)