Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-25T07:42:00.035Z Has data issue: false hasContentIssue false
  • English
  • Français

Graphs whose full automorphism group is a symmetric group

Part of: Graph theory

Published online by Cambridge University Press:  09 April 2009

Martin W. Liebeck
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)}.

MSC classification

Secondary: 05C25: Graphs and abstract algebra (groups, rings, fields, etc.)
Type
Research Article
Information
Journal of the Australian Mathematical Society , Volume 44 , Issue 1 , February 1988 , pp. 46 - 63
Copyright
Copyright © Australian Mathematical Society 1988

References

[1]Frucht, R., ‘Herstellung von Graphen mit vorgegebener abstrakten Gruppe’, Compositio Math. 6 (1938), 239–250.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), 329–336.Google Scholar
[4]Wielandt, H., Finite permutation groups (Academic Press, New York-London, 1964).Google Scholar