section graphs for finite permutation groups参考文献.pdf

JOURNAL OF COMBINATORIALTHEORY 6, 378-386 (1969)
Section Graphs for Finite Permutation Groups
I. Z. BOUWER
National Research Institute for Mathematical Sciences, ., Pretoria, South Africa
Communicated by the Editor-in-Chief
Received January 30, 1968
ABSTRACT
It is shown that for any given finite permutation group P there exist (infinitely many
non-isomorphic) directed and undirected graphs whose automorphism groups contain
P as a subdirect constituent.
1. INTRODUCTION
In the study of the automorphism groups A(X) of graphs X the following
two questions arise:
(i) Given any finite group G: does there exist a graph X such that A(X)
is (abstractly) isomorphic to G ?
(ii) Given any finite permutation group P: does there exist a graph X
such that A(X) is isomorphic, as permutation group, to P ?
Question (i) was put in 1936 by KSnig [5, p. 5]. By suitably modifying
the Cayley color graph of G, Frucht [1] found (undirected) graph con-
structions showing that the answer is yes. Restricting himself to undirected
graphs, Frucht also points out [1, p. 247] that the answer to (ii) is negative,
in general. The same holds for directed graphs. A set of counterexamples
to (ii) is provided by the doubly tr