Strongly Regular Semi-Cayley Graphs
Marialuisa J. de Resmini
and Dieter Jungnickel
DOI: 10.1023/A:1022476321014
Abstract
We consider strongly regular graphs 
= ( V, E) on an even number, say 2 n, of vertices which admit an automorphism group G of order n which has two orbits on V. Such graphs will be called strongly regular semi-Cayley graphs. For instance, the Petersen graph, the Hoffman-Singleton graph, and the triangular graphs T( q) with q 
5 mod 8 provide examples which cannot be obtained as Cayley graphs. We give a representation of strongly regular semi-Cayley graphs in terms of suitable triples of elements in the group ring Z G. By applying characters of G, this approach allows us to obtain interesting nonexistence results if G is Abelian, in particular, if G is cyclic. For instance, if G is cyclic and n is odd, then all examples must have parameters of the form 2 n = 4 s 2 + 4 s + 2, k = 2 s 2 + s, 
= s 2 - 1, and 
= s 2; examples are known only for s = 1, 2, and 4 (together with a noncyclic example for s = 3). We also apply our results to obtain new conditions for the existence of strongly regular Cayley graphs on an even number of vertices when the underlying group H has an Abelian normal subgroup of index 2. In particular, we show the nonexistence of nontrivial strongly regular Cayley graphs over dihedral and generalized quaternion groups, as well as over two series of non-Abelian 2-groups. Up to now these have been the only general nonexistence results for strongly regular Cayley graphs over non-Abelian groups; only the first of these cases was previously known.
= ( V, E) on an even number, say 2 n, of vertices which admit an automorphism group G of order n which has two orbits on V. Such graphs will be called strongly regular semi-Cayley graphs. For instance, the Petersen graph, the Hoffman-Singleton graph, and the triangular graphs T( q) with q 5 mod 8 provide examples which cannot be obtained as Cayley graphs. We give a representation of strongly regular semi-Cayley graphs in terms of suitable triples of elements in the group ring Z G. By applying characters of G, this approach allows us to obtain interesting nonexistence results if G is Abelian, in particular, if G is cyclic. For instance, if G is cyclic and n is odd, then all examples must have parameters of the form 2 n = 4 s 2 + 4 s + 2, k = 2 s 2 + s, = s 2 - 1, and = s 2; examples are known only for s = 1, 2, and 4 (together with a noncyclic example for s = 3). We also apply our results to obtain new conditions for the existence of strongly regular Cayley graphs on an even number of vertices when the underlying group H has an Abelian normal subgroup of index 2. In particular, we show the nonexistence of nontrivial strongly regular Cayley graphs over dihedral and generalized quaternion groups, as well as over two series of non-Abelian 2-groups. Up to now these have been the only general nonexistence results for strongly regular Cayley graphs over non-Abelian groups; only the first of these cases was previously known.Pages: 171–195
Keywords: strongly regular graph; Cayley graph; partial difference set; difference set
Full Text: PDF
References
1. G.M. Adel'son-Vel'skii, B.Ju. Veisfeiler, A.A. Leman, and LA. Faradzev, "Example of a graph without a transitive automorphism group," Soviet Math. Dokl. 10 (1969), 440-441.
2. T. Beth, D. Jungnickel, and H. Lenz, Design Theory, Cambridge University Press, Cambridge, 1986.
3. R.C. Bose, "Strongly regular graphs, partial geometries, and partially balanced designs," Pacific J. Math. 13 (1963), 389-419.
4. W.G. Bridges and R.A. Mena, "Rational circulants with rational spectra and cyclic strongly regular graphs," Ars Combin. 8 (1979), 143-161.
5. W.G. Bridges and R.A. Mena, "Rational G-matrices with rational eigenvalues," J. Combin. Theory Set A 32 (1982), 264-280.
6. P.J. Cameron and J.H. van Lint, Designs, Graphs, Codes and Their Links, Cambridge University Press, Cambridge, 1991.
7. J.E.H. Elliott and A.T. Butson, "Relative difference sets," Illinois J. Math. 10 (1966), 517-531.
8. D. Gorenstein, Finite Groups, Harper and Row, New York, 1968.
9. A.J. Hoffman and R.R. Singleton, "On Moore graphs of diameters 2 and 3," IBM J. Res. Develop. 4 (1960), 497-504.
10. D.R. Hughes, J.H. van Lint, and R.M. Wilson, Unpublished Manuscript (announcement at the 7th British Combinatorial Conference, Cambridge, 1979).
11. B. Huppert, Endliche Gruppen I, Springer, Berlin, 1967.
12. D. Jungnickel, "On automorphism groups of divisible designs," Canad. J. Math. 34 (1982), 257-297.
13. D. Jungnickel, "On automorphism groups of divisible designs II: group invariant generalized conference matrices," Arch. Math. 54 (1990), 200-208.
14. D. Jungnickel, "Difference sets," in Contemporary Design Theory: A Collection of Surveys, J.H. Dinitz and D.R. Stinson, eds., Wiley Interscience, New York, 1992, pp. 241-324.
15. W.M. Kantor, "k-homogeneous groups," Math. Z. 124 (1972), 261-265.
16. S.L. Ma, "Partial differences sets," Discrete Math. 72, (1984), 75-89.
17. S.L. Ma, "Partial difference sets in dihedral groups," South East Asian Bull. Math. 11 (1987), 53-59.
18. S.L. Ma, "On association schemes, Schur rings, strongly regular graphs and partial difference sets,"Ars Combin. 27 (1989), 211-220.
19. D. Marusic, "Strongly regular bicirculants and tricirculants," Ars Combin. 25-C (1988), 11-15.
20. R. Mathon and A. Rosa, "Tables of parameters of BIBDs with r < 41 including existence, enumeration and resolvability results: an update," Ars Combin. 30 (1990), 65-96.
21. T. Schade, "Stark regulare Graphen mit Singergruppe," Diplomarbeit, Universitat Giessen, 1989.
22. M. Suzuki, Group Theory I, Springer, Berlin, 1982.
23. H.P. Yap, Some Topics in Graph Theory, Cambridge University Press, Cambridge, 1986.
2. T. Beth, D. Jungnickel, and H. Lenz, Design Theory, Cambridge University Press, Cambridge, 1986.
3. R.C. Bose, "Strongly regular graphs, partial geometries, and partially balanced designs," Pacific J. Math. 13 (1963), 389-419.
4. W.G. Bridges and R.A. Mena, "Rational circulants with rational spectra and cyclic strongly regular graphs," Ars Combin. 8 (1979), 143-161.
5. W.G. Bridges and R.A. Mena, "Rational G-matrices with rational eigenvalues," J. Combin. Theory Set A 32 (1982), 264-280.
6. P.J. Cameron and J.H. van Lint, Designs, Graphs, Codes and Their Links, Cambridge University Press, Cambridge, 1991.
7. J.E.H. Elliott and A.T. Butson, "Relative difference sets," Illinois J. Math. 10 (1966), 517-531.
8. D. Gorenstein, Finite Groups, Harper and Row, New York, 1968.
9. A.J. Hoffman and R.R. Singleton, "On Moore graphs of diameters 2 and 3," IBM J. Res. Develop. 4 (1960), 497-504.
10. D.R. Hughes, J.H. van Lint, and R.M. Wilson, Unpublished Manuscript (announcement at the 7th British Combinatorial Conference, Cambridge, 1979).
11. B. Huppert, Endliche Gruppen I, Springer, Berlin, 1967.
12. D. Jungnickel, "On automorphism groups of divisible designs," Canad. J. Math. 34 (1982), 257-297.
13. D. Jungnickel, "On automorphism groups of divisible designs II: group invariant generalized conference matrices," Arch. Math. 54 (1990), 200-208.
14. D. Jungnickel, "Difference sets," in Contemporary Design Theory: A Collection of Surveys, J.H. Dinitz and D.R. Stinson, eds., Wiley Interscience, New York, 1992, pp. 241-324.
15. W.M. Kantor, "k-homogeneous groups," Math. Z. 124 (1972), 261-265.
16. S.L. Ma, "Partial differences sets," Discrete Math. 72, (1984), 75-89.
17. S.L. Ma, "Partial difference sets in dihedral groups," South East Asian Bull. Math. 11 (1987), 53-59.
18. S.L. Ma, "On association schemes, Schur rings, strongly regular graphs and partial difference sets,"Ars Combin. 27 (1989), 211-220.
19. D. Marusic, "Strongly regular bicirculants and tricirculants," Ars Combin. 25-C (1988), 11-15.
20. R. Mathon and A. Rosa, "Tables of parameters of BIBDs with r < 41 including existence, enumeration and resolvability results: an update," Ars Combin. 30 (1990), 65-96.
21. T. Schade, "Stark regulare Graphen mit Singergruppe," Diplomarbeit, Universitat Giessen, 1989.
22. M. Suzuki, Group Theory I, Springer, Berlin, 1982.
23. H.P. Yap, Some Topics in Graph Theory, Cambridge University Press, Cambridge, 1986.