zbMATH — the first resource for mathematics

Cores of symmetric graphs. (English) Zbl 1167.05032
Summary: The core of a graph \(\Gamma\) is the smallest graph \(\Delta \) that is homomorphically equivalent to \(\Gamma\) (that is, there exist homomorphisms in both directions). The core of \(\Gamma\) is unique up to isomorphism and is an induced subgraph of \(\Gamma\). We give a construction in some sense dual to the core. The hull of a graph \(\Gamma\) is a graph containing \(\Gamma\) as a spanning subgraph, admitting all the endomorphisms of \(\Gamma\), and having as core a complete graph of the same order as the core of \(\Gamma\). 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 \(\Gamma\) is a non-edge-transitive graph, we show that either the core of \(\Gamma\) is complete, or \(\Gamma\) 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).

05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C15 Coloring of graphs and hypergraphs
05B25 Combinatorial aspects of finite geometries
Full Text: DOI
[1] Dixon, Permutation Groups (1996) · doi:10.1007/978-1-4612-0731-3
[2] Hahn, Graph Symmetry pp 107– (1997) · doi:10.1007/978-94-015-8937-6_4
[3] DOI: 10.1016/0095-8956(84)90056-X · Zbl 0547.05058 · doi:10.1016/0095-8956(84)90056-X
[4] Cameron, Permutation Groups (1999) · Zbl 1091.20002 · doi:10.1017/CBO9780511623677
[5] DOI: 10.1016/B978-044488355-1/50009-8 · doi:10.1016/B978-044488355-1/50009-8
[6] Cameron, Projective and Polar Spaces (1991)
[7] DOI: 10.1016/0097-3165(78)90022-5 · Zbl 0418.05028 · doi:10.1016/0097-3165(78)90022-5
[8] DOI: 10.1007/BF00181359 · Zbl 0282.50019 · doi:10.1007/BF00181359
[9] DOI: 10.1112/blms/18.2.165 · Zbl 0586.20003 · doi:10.1112/blms/18.2.165
[10] DOI: 10.1016/0012-365X(76)90025-X · Zbl 0326.05013 · doi:10.1016/0012-365X(76)90025-X
[11] DOI: 10.1112/plms/s3-54.3.477 · Zbl 0621.20001 · doi:10.1112/plms/s3-54.3.477
[12] DOI: 10.1016/j.tcs.2006.02.003 · Zbl 1097.68054 · doi:10.1016/j.tcs.2006.02.003
[13] DOI: 10.2307/1998750 · Zbl 0514.20033 · doi:10.2307/1998750
[14] DOI: 10.1007/BF01111335 · Zbl 0122.03205 · doi:10.1007/BF01111335
[15] Hell, Graphs and Homomorphisms (2004) · doi:10.1093/acprof:oso/9780198528173.001.0001
[16] Denniston, Atti Accad. Naz. Lincei Rend. Cl. Sci. Fis. Mat. Natur. (8) 52 pp 36– (1972)
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.