Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-05T06:40:27.492Z Has data issue: false hasContentIssue false

Graphs whose full automorphism group is a symmetric group

Published online by Cambridge University Press:  09 April 2009

Martin W. Liebeck
Affiliation:
Department of Mathematics Imperial CollegeLondon S.W.7, England
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We address the problem of describing all graphs Γ such that Aut Γ is a symmetric group, subject to certain restrictions on the sizes of the orbits of Aut Γ on vertices. As a corollary of our general results, we obtain a classification of all graphs Γ on v vertices with Aut Γ ≅ Sn, where ν < min{5n, ½n(n – 1)}.

Type
Research Article
Copyright
Copyright © Australian Mathematical Society 1988

References

[1]Frucht, R., ‘Herstellung von Graphen mit vorgegebener abstrakten Gruppe’, Compositio Math. 6 (1938), 239250.Google Scholar
[2]Gewirtz, A. and Quintas, L. V., ‘Connected extremal edge graphs having symmetric automorphism group’, Recent progress in combinatorics, ed. Tutte, W. T. (Academic Press, New York, 1969).Google Scholar
[3]Heinrich, K. and Wallis, W. D., ‘Graphs with symmetric automorphism group’, J. Graph Theory 2 (1978), 329336.Google Scholar
[4]Wielandt, H., Finite permutation groups (Academic Press, New York-London, 1964).Google Scholar