Strongly regular semi-Cayley graphs

de Resmini, Marialuisa J. ; Jungnickel, Dieter

Journal of Algebraic Combinatorics, Tome 1 (1992) no. 2, pp. 171-195.

Résumé

Summary: We consider strongly regular graphs $Gamma$ = ( 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 $qequiv$ 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, lambda = s ^{2} - 1$, and $mgr = 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.

Détail

Keywords: strongly regular graph, Cayley graph, partial difference set, difference set