Half-Transitive Graphs of Prime-Cube Order
Mingyao Xu
DOI: 10.1023/A:1022440002282
Abstract
We call an undirected graph X half-transitive if the automorphism group Aut X of X acts transitively on the vertex set and edge set but not on the set of ordered pairs of adjacent vertices of X. In this paper we determine all half-transitive graphs of order p 3 and degree 4, where p is an odd prime; namely, we prove that all such graphs are Cayley graphs on the non-Abelian group of order p 3 and exponent p 2, and up to isomorphism there are exactly ( p - 1)/2 such graphs. As a byproduct, this proves the uniqueness of Holt's half-transitive graph with 27 vertices.
Pages: 275–282
Keywords: half-transitive graphs; Cayley graphs; simple groups; Schur multiplier
Full Text: PDF
References
1. B. Alspach, personal communication.
2. B. Alspach, D. MaruSit, and L. Nowitz, "Constructing graphs which are 1/2 -transitive," J. Austral. Math. Soc., to appear.
3. B. Alspach and T.D. Parsons, "A construction for vertex-transitive graphs," Canad. J. Math. 34 (1982), 307-318.
4. L. Babai, "Isomorphism problem for a class of point-symmetric structures," Acta Math. Acad. Sci. Hungar. 29 (1977), 329-336.
5. I.Z. Bouwer, "Vertex and edge-transitive but not 1-transitive graphs," Canad. Math. Bull. 13 (1970), 231-237.
6. J.H. Conway, R.T. Curtis, S.P. Norton, R.A. Parker, and R.A. Wilson, Atlas of Finite Groups, Oxford University Press, Oxford, 1985.
7. C.D. Godsil, "On the full automorphism group of a graph," Combinatorica 1 (1981), 243-256.
8. D. Gorenstein, Finite Simple Groups, Plenum Press, New York, 1982.
9. F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1969.
10. D.F. Holt, "A graph which is edge transitive but not arc-transitive," J. Graph Theory 5 (1981), 201-204.
11. B. Huppert, Endliche Gruppen I, Springer-Verlag, Berlin, 1967.
12. D. Marusic, "Vertex transitive graphs and digraphs of order pk," Ann. Discrete Math. 27 (1985), 115-128.
2. B. Alspach, D. MaruSit, and L. Nowitz, "Constructing graphs which are 1/2 -transitive," J. Austral. Math. Soc., to appear.
3. B. Alspach and T.D. Parsons, "A construction for vertex-transitive graphs," Canad. J. Math. 34 (1982), 307-318.
4. L. Babai, "Isomorphism problem for a class of point-symmetric structures," Acta Math. Acad. Sci. Hungar. 29 (1977), 329-336.
5. I.Z. Bouwer, "Vertex and edge-transitive but not 1-transitive graphs," Canad. Math. Bull. 13 (1970), 231-237.
6. J.H. Conway, R.T. Curtis, S.P. Norton, R.A. Parker, and R.A. Wilson, Atlas of Finite Groups, Oxford University Press, Oxford, 1985.
7. C.D. Godsil, "On the full automorphism group of a graph," Combinatorica 1 (1981), 243-256.
8. D. Gorenstein, Finite Simple Groups, Plenum Press, New York, 1982.
9. F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1969.
10. D.F. Holt, "A graph which is edge transitive but not arc-transitive," J. Graph Theory 5 (1981), 201-204.
11. B. Huppert, Endliche Gruppen I, Springer-Verlag, Berlin, 1967.
12. D. Marusic, "Vertex transitive graphs and digraphs of order pk," Ann. Discrete Math. 27 (1985), 115-128.