×

zbMATH — the first resource for mathematics

Cores of geometric graphs. (English) Zbl 1234.05165
Summary: 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.

MSC:
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05E30 Association schemes, strongly regular graphs
05B15 Orthogonal arrays, Latin squares, Room squares
51E14 Finite partial geometries (general), nets, partial spreads
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Beth, T., Jungnickel, D., Lenz, H.: Design Theory. Bibliographisches Institut, Mannheim (1985) · Zbl 0569.05002
[2] Blokhuis A., Brouwer A.E.: Locally 4-by-4 grid graphs. J. Graph Theory 13(2), 229–244 (1989) · Zbl 0722.05054 · doi:10.1002/jgt.3190130209
[3] Bose R.C.: Strongly regular graphs, partial geometries and partially balanced designs. Pacific J. Math. 13, 389–419 (1963) · Zbl 0118.33903 · doi:10.2140/pjm.1963.13.389
[4] Brouwer A.E., Cohen A.M., Neumaier A.: Distance-Regular Graphs. Springer-Verlag, Berlin (1989) · Zbl 0747.05073
[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) · Zbl 1167.05032 · doi:10.1017/S1446788708000815
[7] Godsil C., Royle G.: Algebraic Graph Theory. Springer-Verlag, New York (2001) · Zbl 0968.05002
[8] Hahn, G., Tardif, C.: Graph homomorphisms: structure and symmetry. In: Graph Symmetry, pp. 107–166. Kluwer Acad. Publ., Dordrecht (1997) · Zbl 0880.05079
[9] Hell P., Nešetřil 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) · Zbl 0516.05010
[11] Neumaier, A.: Strongly regular graphs with smallest eigenvalue . Arch. Math. (Basel) 33(4), 392–400 (1979/80) · Zbl 0407.05043
[12] Payne S.E., Thas J.A.: Finite Generalized Quadrangles. MA, Boston (1984) · Zbl 0551.05027
[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) · Zbl 0986.51005
[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)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.