Almost all graphs are rigid—revisited |
| |
Authors: | Jens Ktters |
| |
Institution: | aFaculty of Information Technology, Monash University, Clayton, Victoria 3800, Australia |
| |
Abstract: | It is shown that almost all graphs are unretractive, i.e. have no endomorphisms other than their automorphisms. A more general result has already been published in V. Koubek, V. Rödl, On the minimum order of graphs with given semigroup, J. Combin. Theory Ser. B 36 (1984) 135–155]. In the paper at hand, a different proof is presented, following an approach of P. Erdős and A. Rényi that was used in their proof P. Erdős, A. Rényi, Asymmetric graphs, Acta Math. Acad. Sci. Hungar. 14 (1963) 295–315] that almost all graphs are asymmetric (have a trivial automorphism group). The approach is modified using an algebraically motivated reduction to idempotent endomorphisms. These take the role of the automorphisms in the proof of Erdős and Rényi. A bound of is provided for the ratio of retractive graphs among all graphs with n vertices, confirming an earlier statement by Babai L. Babai, Automorphism groups, isomorphism, reconstruction, in: R.L. Graham, M. Grötschel, L. Lovász (Eds.), in: Handbook of Combinatorics, vol. 2, Elsevier, Amsterdam, 1995, pp. 1447–1540]. The fact that almost all graphs are unretractive and asymmetric can be summarized in the statement that almost all graphs are rigid (have a trivial endomorphism monoid), and the same bound can be obtained for corresponding ratios of nonrigid graphs. |
| |
Keywords: | Almost all graphs Rigid graphs Unretractive graphs |
本文献已被 ScienceDirect 等数据库收录! |
|