|
Organizers |
Are almost all graphs rigid?
by
Jens Kötters
Alexanderstr. 159, 26121 Oldenburg
A graph is called asymmetric if it has the identity mapping as its only automorphism. It is proven in [1] that almost all graphs are asymmetric. A graph is called rigid if it has the identity mapping as its only endomorphism, which is a stronger property than asymmetry. By adopting the approach of Erdös and Renyi, it can be shown that almost all graphs are rigid.
References: [1] P.Erdös and A.Renyi, Asymmetric Graphs, Acta Math. Acad. Sci. Hungar.14 (1963) 295-315
Date received: May 21, 2004
Copyright © 2004 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Mathematical Conference Abstracts. Document # canq-93.