Geodesic
On Rigid Undirected Graphs
Canadian journal of mathematics, Tome 18 (1966) no. 1, pp. 1237-1242

Voir la notice de l'article provenant de la source Cambridge University Press

By an undirected graph we mean a couple (X, R), where X is a set and R is a subset of X × X such that (x, y) ∈ R implies (y, x) ∈ R. The cardinal of X, denoted by |X|, will be called the cardinal of the graph.A mapping f:X → X is called an endomorphism of (X, R) if (x, y) ∈ R implies that (f(x), f(y)) ∈ R for all x, y ∈ R.An undirected graph (X, R) is called rigid if there is only one endomorphism of (X, R), namely the identity mapping of X.P. Erdös communicated orally that, using probability methods, it is possible to prove that almost all finite undirected graphs are rigid. 
Hedrlín, Z.; Pultr, A. On Rigid Undirected Graphs. Canadian journal of mathematics, Tome 18 (1966) no. 1, pp. 1237-1242. doi: 10.4153/CJM-1966-121-7
@article{10_4153_CJM_1966_121_7,
     author = {Hedrl{\'\i}n, Z. and Pultr, A.},
     title = {On {Rigid} {Undirected} {Graphs}},
     journal = {Canadian journal of mathematics},
     pages = {1237--1242},
     year = {1966},
     volume = {18},
     number = {1},
     doi = {10.4153/CJM-1966-121-7},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-1966-121-7/}
}
TY  - JOUR
AU  - Hedrlín, Z.
AU  - Pultr, A.
TI  - On Rigid Undirected Graphs
JO  - Canadian journal of mathematics
PY  - 1966
SP  - 1237
EP  - 1242
VL  - 18
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CJM-1966-121-7/
DO  - 10.4153/CJM-1966-121-7
ID  - 10_4153_CJM_1966_121_7
ER  - 
%0 Journal Article
%A Hedrlín, Z.
%A Pultr, A.
%T On Rigid Undirected Graphs
%J Canadian journal of mathematics
%D 1966
%P 1237-1242
%V 18
%N 1
%U http://geodesic.mathdoc.fr/articles/10.4153/CJM-1966-121-7/
%R 10.4153/CJM-1966-121-7
%F 10_4153_CJM_1966_121_7

[1] 1. Hedrlin, Z. and Pultr, A., Symmetric relations (undirected graphs) with given semigroups, Monatsh. Math., 69 (1965), 318–322. Google Scholar

[2] 2. Kagno, I. N., Linear graphs of degree ≤6 and their groups, Amer. J. Math., 68 (1946), 505–520. Google Scholar

[3] 3. Vopĕnka, P., Pultr, A., and Hedrlín, Z., A rigid relation exists on any set, Comment. Math. Univ. Carolinae, 6 (1965), 149–155. Google Scholar

Cité par Sources :