Czech Digital Mathematics Library (Institute of Mathematics CAS) · 1965 · 10 citations · 0 references
Open access
Natural SciencesMathematicsCombinatoricsDiscrete MathematicsTopologyCombinatorial Game TheoryCombinatorial Set TheoryGeometric GraphsGraph TheoryEnumerative Graph Theory
Let V be a non-void set and a binary relation on V, ECVx.V Let f be a transformation of V .If (x,y)e.E implies (f (x) jf (y)) e , then f is called compatible with the relation Let C(l) denote the set of all transformations compatible with a relation Then C() with the binary operation O ( O is defined, as usual, by the compositions of transformations) is a semigroup, and its unity element is the 1dentity transformation.The pair[V,E] will be considered as a graph, where V is the set of vertices, the set of edges* The transformations in C(E) will be called endomorphisms of [V,E] If, for every x,y c V , precisely one of the cases (x,y)c f Cy,x)e holds, then the graph [ V,E J is called a tournament* We emphasize that a tournament contains all loops; thus every constant transformation is an endomorphisnu An f C(E) is called an automorphism of the graph [V',E ] if f is 1-1 mapping; an feC(E) is calledjfcproper endomorphism of the graph [V,E] if f is not 1-1* Let C(E) contain I Vl+1 elements (here IV| denotes the car.dinal of V ), namely the identity and all the constant transformations of V .Then the graph [ V, ] is calx) We remark that the expression "rigid graph" is often used in a different sense* -429 -