On a Class of Fixed-Point-Free Graphs
Gert Sabidussi · Proceedings of the American Mathematical Society · 1958
A number of papers [l; 2; 3; 4] have dealt with the construction of finite graphs X whose automorphism group G(X) is isomorphic to a given finite group G. Examination of the graphs constructed in these papers shows the following two facts.(1) The graphs X have the property that for any two vertices x and y of X there is at most one 4>EG(X) which sends x into y ((1) is precisely the fact which is used in [l] and [2] to prove that G(X) actually is isomorphic to G).(2) The graphs X are modifications of Cayley color-groups of the given group G with respect to some set H of generators of G (cf. Definition 2 below) in the sense that the vertices and edges of the color-group are replaced by certain graphs (cf.Definition 3).It is the purpose of the present note to show that (1) implies (2) (Theorem 3).By a graph X we mean a finite set V together with a set £ of unordered pairs of distinct elements of V. We shall indicate unordered pairs by brackets.The elements of V are called the vertices of X, the elements of £ the edges of X.To distinguish between different graphs we shall always write V(X) for V, and E(X) for E. By G(X) we denote the automorphism group of X.We shall consider the elements of G(X) as permutations of the vertices of X.