Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-29T05:58:05.807Z Has data issue: false hasContentIssue false
  • English
  • Français

CORES OF SYMMETRIC GRAPHS

Part of: Designs and configurations Graph theory

Published online by Cambridge University Press:  01 October 2008

PETER J. CAMERON  and
PRISCILA A. KAZANIDIS
PETER J. CAMERON*
Affiliation:
School of Mathematical Sciences, Queen Mary, University of London, London E1 4NS, UK (email: [email protected])
PRISCILA A. KAZANIDIS
Affiliation:
Institute of Mathematics, College of Science, University of the Philippines Diliman, Quezon City 1101, Philippines (email: [email protected])
*
✉For correspondence; e-mail: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

The core of a graph Γ is the smallest graph Δ that is homomorphically equivalent to Γ (that is, there exist homomorphisms in both directions). The core of Γ is unique up to isomorphism and is an induced subgraph of Γ. We give a construction in some sense dual to the core. The hull of a graph Γ is a graph containing Γ as a spanning subgraph, admitting all the endomorphisms of Γ, and having as core a complete graph of the same order as the core of Γ. This construction is related to the notion of a synchronizing permutation group, which arises in semigroup theory; we provide some more insight by characterizing these permutation groups in terms of graphs. It is known that the core of a vertex-transitive graph is vertex-transitive. In some cases we can make stronger statements: for example, if Γ is a non-edge-transitive graph, we show that either the core of Γ is complete, or Γ is its own core. Rank-three graphs are non-edge-transitive. We examine some families of these to decide which of the two alternatives for the core actually holds. We will see that this question is very difficult, being equivalent in some cases to unsolved questions in finite geometry (for example, about spreads, ovoids and partitions into ovoids in polar spaces).

Keywords

graph homomorphismcore graphrank three graph

MSC classification

Secondary: 05C25: Graphs and abstract algebra (groups, rings, fields, etc.) 05B25: Finite geometries
Type
Research Article
Information
Journal of the Australian Mathematical Society , Volume 85 , Issue 2 , October 2008 , pp. 145 - 154
Copyright
Copyright © 2008 Australian Mathematical Society

References

[1]Araújo, João, ‘A group theoretical approach to synchronizing automata and the Černý problem’, Preprint, Lisbon, January 2008.Google Scholar
[2]Arnold, Fredrick and Steinberg, Benjamin, ‘Synchronizing groups and automata’, Theoret. Comput. Sci. 359 (2006), 101–110.CrossRefGoogle Scholar
[3]Baker, R. D., ‘Partitioning the planes of AG2m(2) into 2-designs’, Discrete Math. 15 (1976), 205–211.CrossRefGoogle Scholar
[4]Beutelspacher, A., ‘On parallelisms in finite projective spaces’, Geom. Dedicata 3 (1974), 35–40.CrossRefGoogle Scholar
[5]Cameron, Peter J., Projective and Polar Spaces, QMW Maths Notes, 13 (Queen Mary and Westfield College, London, 1991).Google Scholar
[6]Cameron, Peter J., Permutation Groups, London Mathematical Society Student Texts, 45 (Cambridge University Press, Cambridge, 1999).CrossRefGoogle Scholar
[7]Denniston, R. H. F., ‘Some packings of projective spaces’, Atti Accad. Naz. Lincei Rend. Cl. Sci. Fis. Mat. Natur. (8) 52 (1972), 36–40.Google Scholar
[8]Dixon, J. D. and Mortimer, B., Permutation Groups, Graduate Texts in Mathematics, 163 (Springer, New York, 1996).CrossRefGoogle Scholar
[9] The Group, ‘ — Groups, Algorithms, and Programming’, Version 4.4.9, 2006; see http://www.gap-system.org.Google Scholar
[10]Godsil, Chris  and Royle, Gordon F., ‘Cores of geometric graphs’, Preprint, Waterloo, ON, Canada, March 2008.Google Scholar
[11]Hahn, Geňa and Tardif, Claude, ‘Graph homomorphisms: structure and symmetry’, in: Graph Symmetry, NATO Advanced Science Institute, Series C, Mathematical and Physical Sciences, 497 (eds. G. Hahn and G. Sabidussi) (Kluwer Academic, Dordrecht, 1997), pp. 107–166.CrossRefGoogle Scholar
[12]Hell, Pavol and Nešetřil, Jaroslav, Graphs and Homomorphisms (Oxford University Press, Oxford, 2004).CrossRefGoogle Scholar
[13]Higman, D. G., ‘Finite permutation groups of rank 3’, Math. Z. 86 (1964), 145–156.CrossRefGoogle Scholar
[14]Kantor, W. M. and Liebler, R. A., ‘The rank 3 permutation representations of the finite classical groups’, Trans. Amer. Math. Soc. 271 (1982), 1–71.CrossRefGoogle Scholar
[15]Liebeck, M. W., ‘The affine permutation groups of rank three’, Proc. London Math. Soc. (3) 54 (1987), 477–516.CrossRefGoogle Scholar
[16]Liebeck, M. W. and Saxl, J., ‘The finite primitive permutation groups of rank three’, Bull. London Math. Soc. 18 (1986), 165–172.CrossRefGoogle Scholar
[17]Lovász, L., ‘Kneser’s conjecture, chromatic number, and homotopy’, J. Combin. Theory Ser. A 25 (1978), 319–324.CrossRefGoogle Scholar
[18]Neumann, Peter M., ‘Primitive permutation groups and their section-regular partitions’, Michigan Math. J. to appear.Google Scholar
[19]Soicher, L. H., ‘The GRAPE package for GAP’, Version 4.3, 2006,http://www.maths.qmul.ac.uk/∼leonard/grape/.Google Scholar
[20]Thas, J. A., ‘Projective geometry over a finite field’, in: Handbook of Incidence Geometry (ed. F. Buekenhout) (Elsevier, Amsterdam, 1995), pp. 295–347.CrossRefGoogle Scholar
[21]Welzl, E., ‘Symmetric graphs and interpretations’, J. Combin. Theory B 37 (1984), 235–244.CrossRefGoogle Scholar