Hostname: page-component-78c5997874-lj6df Total loading time: 0 Render date: 2024-11-07T05:18:01.505Z Has data issue: false hasContentIssue false

An algebraic characterization of symmetric graphs with a prime number of vertices

Published online by Cambridge University Press:  17 April 2009

J.L. Berggren
Affiliation:
Department of Mathematics, Simon Fraser University, Burnaby, British Columbia, Canada.
Rights & Permissions [Opens in a new window]

Extract

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.

A graph Γ is called symmetric if its automorphism group is transitive on its vertices and edges. Let p be an odd prime, Z(p) the field of integers modulo p, and Z*(p) = (aZ(p) | a ≠ 0}, the multiplicative subgroup of Z(p). This paper gives a simple proof of the equivalence of two statements:

(1) Γ is a symmetric graph with p vertices, each having degree n ≥ 1;

(2) the integer n is an even divisor of p − 1 and Γ is isomorphic to the graph whose vertices are the elements of Z(p) and whose edges are the pairs {a, a+h} where aZ(p) and hH, the unique subgroup of Z*(p) of order n.

In addition, the automorphism group of Γ is determined.

Type
Research Article
Copyright
Copyright © Australian Mathematical Society 1972

References

[1]Berggren, J.L., “An algebraic characterization of finite symmetric tournaments”, Bull. Austral. Math. Soc. 6 (1972), 5359.CrossRefGoogle Scholar
[2]Chao, Chong-yun, “On groups and graphs”, Trans. Amer. Math. Soc. 118 (1965), 488497.CrossRefGoogle Scholar
[3]Chao, Chong-yun, “On the classification of symmetric graphs with a prime number of vertices”, Trans. Amer. Math. Soc. 158 (1971) 247256.CrossRefGoogle Scholar
[4]Passman, Donald, Permutation groups (W.A. Benjamin, New York, Amsterdam, 1968).Google Scholar
[5]Turner, James, “Point-symmetric graphs with a prime number of points”, J. Combinatorial Theory 3 (1967), 136145.CrossRefGoogle Scholar