ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ars mathematica contemporanea 8 (2015) 195-213
Strongly regular m-Cayley circulant graphs and digraphs
Luis Martinez *
University of the Basque Country UPV/EHU, Department of Mathematics, 48080 Bilbao, Spain
Received 16 September 2013, accepted 21 September 2014, published online 17 December 2014
The first part of this paper is a survey about strongly regular graphs and digraphs admitting a semiregular cyclic group of automorphisms. In the second part, some new types of such digraphs, called uniform and almost uniform, are studied. By using partial sum families, the form of the parameters is determined and some directed strongly regular graphs derived from these partial sum families with previously unknown parameters are obtained.
Keywords: m-Cayley, circulant, strongly regular graphs, strongly regular digraphs, uniform partial sum families, almost-uniform partial sum families.
Math. Subj. Class.: 05Cxx, 05C20, 05C25, 05C50, 05E30
1 Introduction
Strongly regular graphs, which we define below, were introduced by Bose [4] in 1963. They constitute a very important class of graphs; in fact, they are one of the most basic association schemes, more specifically, they are the ones with two classes.
Definition 1.1. A graph X without loops of valency k and order v is called a strongly regular graph with parameters v, k, A, p (for short, (v, k, A, p)-SRG) if any two adjacent vertices have exactly A common neighbours and any two distinct non-adjacent vertices have exactly p common neighbours.
A SRG graph X is said to be trivial if X or its complement is a disjoint union of complete graphs.
* Supported by the Spanish Government, grant MTM2011-28229-C02-02 and by the Basque Government, grant IT753-13. Technical and human support provided by IZO-SGIker (UPV/EHU, MICINN, GV/EJ, ESF) is gratefully acknowledged. Dedicated to the memory of my mother.
E-mail address: luis.martinez@ehu.es (Luis Martinez)
Abstract
©® This work is licensed under http://creativecommons.Org/licenses/by/3.0/
196
Ars Math. Contemp. 8 (2015) 215-223
It is well known that if a non-trivial SRG is not a conference graph, that is, if the parameters are not of the form k = (v - l)/2,p = (v - l)/4, A = (v - 5)/4, then the eigenvalues of an adjacency matrix are integer numbers, and consequently A = ft2 + 4y, where ft = A- p and y = k - p, is also an integer.
The problem of studying what SRGs have nice cyclic automorphism groups has received a considerable attention over the past decades.
A group of automorphisms of a graph is said to be regular if it acts transitively on the set of vertices and all the stabilizers are trivial. A graph is called circulant if it admits a cyclic regular group of automorphisms.
By a classical result of W.G. Bridges and R.A. Mena [5] it is known that the Paley graphs are the only non-trivial circulant strongly regular graphs.
Given integers m > l and n > 2, an automorphism group of a graph is called (m, n)-semiregular if it has m orbits of length n and no other orbit, and the action is regular on each orbit. An m-Cayley graph X is a graph admitting an (m,n)-semiregular group H of automorphisms. When H is abelian, we say that X is m-Abelian. If H is generated by an automorphism p (that is to say, when H is a cyclic group) and m = l (respectively, m = 2) we say that X is n-circulant (respectively, n-bicirculant). Sometimes, when a graph is m-Cayley over a cyclic group, we will just say that the graph is 'm-Cayley circulant', although that this terminology does not mean that the graph admits a regular group of automorphisms and should not be confused with the definition of circulant graph. Every m-Cayley graph X can be represented, following the terminology established by A. Malnic et al. in [18], by an m x m array of subsets of H in the following way. Let U0,..., Um_i be the m orbits of H, and for each i let u € Uj. For each i and j, let Sjj be defined by Sjj = {p e H | Wj -»• p(wj)}. The family (Sjj) is called the symbol of £ relative to (H; wo,..., Wm-1).
The notion of strongly regular graph was generalized for directed graphs by Duval in [6]. A directed graph X without loops, of order v in which every vertex has both in-degree and out-degree k is called a directed strongly regular graph with parameters (v, k, p, A, t) (for short, (v, k, p, A, t) -DSRG or simply DSRG if we do not specify the parameters) whenever for any vertex u of X there are t undirected edges having u as an endvertex and for every two different vertices u and w of X the number of paths p(u, w) of length 2 starting at u and ending at w depends only on whether uw is an arc of X or not. In particular,
(where A(X) denotes the arc set of X). A directed strongly regular graph will also be refereed to as a strongly regular digraph.
DSRGs have received a considerable attention in the literature (see, for instance, [7], [8], [9], [11], [12], [13], [14]).
The following relation between the parameters of a DSRG is obvious:
k(k — ft) = pv + y,
where ft = A - p and y = t - p.
It is well known that ft2 + 4y is a square, unless
(1.1)
k = t= (v- l)/2,p= (v- l)/4,A= (v- 5)/4,
(1.2)
Luis Martinez: Strongly regular m-Cayley circulant graphs and digraphs	197
in which case the graph is undirected and is a conference graph, or
k = {v- l)/2, + I)/A, \=(v- 3)/4, t = 0.	(1.3)
We define	_
A = yjp2 + 4y ,
which is an integer if the parameters of the digraph are not as indicated above.
A DSRG X is called trivial if k = t and X is trivial as an undirected SRG.
Next, we will review the main results in this paper. In the first part of this paper we will make a review of the study of strongly regular graphs and digraphs which are m-Cayley over a cyclic group (m-Cayley circulant SRGs and DSRGs). In Section 2 we will focus on the undirected graphs, and in Section 3 on the more general case of directed graphs.
In the second part we will present some new results on two structures that produce circulant m-Cayley DSRGs. We study in Sections 4,5 and 6 the first structure, uniform partial sum families, which was proposed in the last section of [2], and we obtain there the general form of the parameters for the circulant case and give an sporadic uniform partial sum family which originates a DSRG with parameters previously undecided. In Section 7, we study almost uniform partial sum families, which are a generalization of uniform partial sum families, and obtain again the form of the parameters for the circulant case. Finally, we use almost uniform partial sum families to obtain three DSRG with parameters previously undecided.
2 Semiregular SRGs over cyclic groups
In this section we will focuss on undirected graphs. In particular, we will review some results on strongly regular graphs admitting cyclic semiregular groups of automorphisms.
Probably, the systematic study of circulant SRGs was began by D. Marusic in his seminal paper [21]. There, he obtained the form of the parameters of such graphs for the bicirculant case.
Proposition 2.1. If a non-trivial (2 n, k,\,^) bicirculant strongly regular graph exists with prime n then, up to complementation, the parameters of the graph are
v = 2n = 4s2 + 4s + 2, k = 2s2 + s,\=s2-
He determined also some properties of the elements of the symbol. He denoted S0, o, S1,1 and S0,1 by R, S and T, respectively, and he proved that the non-zero elements of the cyclic group Cn are the disjoint union of R and S, and that |R| = |S| = s2 + s and |T| = s2. He found also examples of such graphs for s = 1 and s = 2.
He considered also non-trivial tricirculant SRGs over a cyclic group Cn of prime order and proved that, for such a graph or its complement, the elements of the symbol S0 0, S11 and S2 2 form a partition of the set of non-zero elements of Cn.
His results were generalized by De Resmini and Jungnickel in [22]. They proved that the form of the parameters of a non-trivial bicirculant SRG over a cyclic group of order n was the one indicated in Proposition 2.1 if n is odd or not divisible by A. They found also one such graph for s = 4. Unfortunately, the technique that they used to construct the graph, which is based on the existence of certain difference families over cyclic groups, was not fruitful to get examples with s > 5.
198
Ars Math. Contemp. 8 (2015) 215-223
This was further generalized by K.H. Leung and S.L. Ma in [17]. They found the general form of the parameters of non-trivial bicirculant SRGs, as stated in the following proposition, where c = |S0,i|, d = |S0,01:
Proposition 2.2. Up to complementation, the parameters for any non-trivial bicirculant SRG over a cyclic group of order n are the following:
1.	(n; c, d; A,	= (2m2 + 2m + 1; m2, m2 + m; m2 ^ 1, m2) where m > 1.
2.	(n; c, d; A,	= (2m2; m2, m2 ^ m; m2 ^ m; m2 — m) where m > 2.
3.	(n; c, d; A,	= (2m2; m2, m2 + m; m2 + m; m2 + m) where m > 3.
4.	(n; c, d; A,	= (2m2; m2 ± m, m2; m2 ± m; m2 ± m) where m > 2.
Besides the graphs found by Marusic and by De Resmini and Jungnickel, Leung and Ma found one example for m = 2 in family 2 and one example for m = 2 in family 4 of the previous proposition. They also proved the non-existence of bicirculants SRG over cyclic groups of order 2m2 where m = pru,p is a prime congruent to 3 modulo 4, p and u are relatively prime and u2 < pr.
More bicirculant SRGs were found by A. Malnic et al. in [19]. Concretely, they obtained bicirculant SRGs with parameters of the same form as in Proposition 2.1 for s = 3,4 and 5. The graphs that they found were the first known pairs of complementary bicirculant SRGs which are vertex-transitive but not edge-transitive.
K. Kutnar et al. studied tricirculant SRGs in [16]. They proved that, under certain appropriate conditions, the elements on the symbol of a tricirculant SRG over a cyclic group Cn satisfy that S0,0, S1,1, S2,2 form a partition of Cn - {0} and the parameters of the graph can be determined. They denoted S0,0, S1,1, S2,2, S0,1, S1,2 and S2,0 by A, B, C, R, S and T, respectively (the other elements in the symbol can be easily determined from these ones), and they denoted by TCay(C„; A, B, C; R, S, T) the associated tricirculant. In the next proposition, for a subset D £ Cn, we set D = Cn \ (S u {0}).
Proposition 2.3. Let X = TCay(C„;(A, B, C; R, S, T) be a non-trivial (3n, k, A, -strongly regular tricirculant, where |A| + |B| + |C| < | A| + |B| + |C|. Assume A u B u C f 0. If n is a prime or n is coprime to 6A then there exists an integer s such that the following two statements hold.
1.	If the cardinalities of A, B and C are not all equal, then
(3n, k, A, = (3(12s2 + 9s + 2), (4s + 1)(3s + 1), s(4s + 3), s(4s + 1)).
If in addition |A| = |C| ^ |B| (which is equivalent to |R| = |S| ^ |T|), then
|A| = 2s( 1 + 2s), |B| = (4s + 0(s + 1), |R| = s(4s + 1) and |T| = (1 + 2s)2.
2.	If A B C then
(3n, k, A, = (3(3s2 ^ 3s + 1), s(3s ^ 1), s2 + s ^ 1, s2).
In this case A s s 1 and R S T s2.
When A = \C\f |B| they proved that, for s = -1, exactly one tricirculant SRG exists up to isomorphisms, and for s = 1 no such graph exists.
When A B C they proved that for s 2 exactly one tricirculant SRG exists up to isomorphisms, and for s 3 exactly four exist, and that for s 2 no such graph exists.
Luis Martinez: Strongly regular m-Cayley circulant graphs and digraphs	199
3 Semiregular DSRGs over cyclic groups
DSRGs admitting a semiregular group of automorphisms were studied by Martinez and Araluze in [20] by using the concept of partial sum family. In the next definition, the third identity holds in the group ring Z[H]. As usual, we will identify a subset of H with the sum in Z[H] of its elements.
Definition 3.1. Let H be a group of order n and let m be an integer with m > 1. A family S = {Sj, with 0 < i, j < m, of subsets of H is a (m,n, k,^, A, t)-partial sum family (for short, (m, n, k, A, t)-PSF, or simply PSF if we do not specify the parameters) if it satisfies:
1.	for every i it holds that 0 ^ S^, where 0 is the identity of H.
2.	for every i it holds that £ "01 |Sj = j01 |SjVi| = k
3.	for every i and j it holds that £[01 Si,jS^; = Si,j0} + ftSij + ^H, where Si,j is the Kronecker delta, and where 7 = i - ^ and = A -
The symbol notation, presented in the introduction for undirected graphs, is valid also for directed graphs. Martinez and Araluze proved that the existence of a (m, n, k, A, t)-partial sum family over a group H is equivalent to the existence of a (mn, k, A, t)-DSRG which admits a group of automorphisms isomorphic to H acting semiregularly and with m orbits (in fact, the elements of the PSF form the symbol of the digraph).
They found 17 new DSRGs by using partial sum families. 14 of them had cyclic groups as groups of automorphisms, which are the kind of digraphs that we are considering in this paper. More specifically, they found:
Four PSFs with parameters (2,15,13,6,5,8), (2,17,14,6,5,12), (2,17,15,7,6,9), (2,20,17,8,6,11) which produce bicirculant digraphs.
Five PSFs with parameters (3,9,10,4,3,6), (3,11,11,4,3,4), (3,13,10,3,1,6), (3,14,14,5,4,5), (3,15,14,4,5,6) which produce tricirculant digraphs.
Four PSFs with parameters (4,7,7,2,1,2), (4,8,9,3,1,6), (4,8,10,3,3,7), (4,11,10,2,3,4) which produce tetracirculant digraphs.
One PSF with parameters (5,7,8,2,1,4) which produce a pentacirculant digraph.
Finally, Araluze et al. found in [2] the form of the possible parameters of bicirculant DSRGs. They called the partial sum families partial sum quadruples in this case when m = 2.
Proposition 3.2. Let S be a non-trivial PSQ in a cyclic group H. Then, up to complementation, the parameters of S are of the following form, where U = k - i and s, f are positive integers, and where q = |S1,0 and r = |S0,01:
1.	n=s( 2f + 1), q= sf, r = sf, k = 2sf,^ = sf, A = sf - 1) ,t = sf.
2.	n=s( 2f + 1), q= s(f + 1), r = sf,k = s( 2f + 1) ,M = s(f + 1) ,A = sf,t = s(f + 1).
3.	n = 4s, q = 2s, r = 2s - 1, k = 4s ^ 1, ^ = s, A = 3s - 2, t = 3s - 1.
4.	n = 2s2 +2s+ 1+2U, q = s2 +U, r = s2 +s+U,k = 2s2+s+2U,,u= s2 +U, A = s2-1 +U and t = 2s2 + s + U.
5.	n = 2s2 + 2U, q = s^ U, r = s^ s + U,k = 2s2 + s + 2U,^= s2 + s + U,A = s2 + s + U and t = 2s2 + s + U, where 2s divides s2 + U.
200
Ars Math. Contemp. 8 (2015) 215-223
6.	n = 2 s2 + 2 U, q = s2 + U, r = s2^ s + U,k = 2 s2^ s + 2U,p=s2- s + U,A = s2 - s + U and t = 2s2 - s + U, where 2s divides s2 + U.
7.	n = 2s2 + 2U, q = s2± s + U, r = s^ U, k = 2s2 ± s + 2U,^= s2± s + U, A = s2 ± s + U and t = 2s2 ± s + U, where s divides U.
8.	n = 4s2,q = 2s2 ±2s,r = 2s2 ±s,k = 4s2 ±3s, ^ = (s±1)(2s±1),A = (s±1)(2s± 1) and t = s2 + (s ± 1)(2s ± 1)
Families 4,5,6 and 7 correspond with the ones found by Leung and Ma in 2.2 (in fact, they correspond to the particular case U = 0). Araluze et al. proved that PSQs with parameters as in families 1,2 and 3 exists for every s and f. They found several sporadic examples for the other families, two of which produced DSRGs not isomorphic to any known ones with that parameters.
Finally, we will mention a result about bicirculant association schemes. Let us recall first the definition of association scheme.
An association scheme of class s is a pair X = (X, R, where R = {R0, ...,RS} is a partition of X2 that satisfies:
1.	Ro = {(x, x) | x € X}.
2.	For every i = 0,..., n, we have {(y, x) | (x, y) € R} € R.
3.	For every i,j,k = 0,..., n, there exists a non-negative integer pkj such that | {z € X | (x,z) € Ri, (z,y) € Rj}| = pj whenever (x,y) € Rfc.
The cardinality of X is called the order of the association scheme. The Ri are called the basic relations of the association scheme, and the (X, Ri) are called the basic digraphs. It is an easy consequence of part 3 of the definition that all the basic digraphs (X, Ri) are regular. The degree of Ri is defined as the degree of X, Ri . The association schemes of class one are called trivial.
The linear span C[R of the adjacency matrices of the Ri is called the Bose-Mesner algebra of the association scheme. The vector space CX is a left C[R-module in a natural way. Since C[R is a semisimple algebra, the mentioned vector space CX decomposes as a direct sum of irreducible C[R-submodules, which are called the irreducible representations of X.
An association scheme X = (X,{R0,..., Rs}) is said to be primitive if all the Ri are strongly connected.
An automorphism of an association scheme X = (X,{R0,..., Rs}) is a bijection of X that is an automorphism of all the digraphs corresponding to the relations Ri. An association scheme X = (X,{R0,..., Rs}) is said to be bicirculant if there exists a cyclic group of automorphisms of X which acts semiregularly on X and has 2 orbits.
I. Kovacs et al. obtained in [15] the following result:
Proposition 3.3. Let X be a primitive bicirculant scheme on 2pe points, p > 2 a prime. Then
1.	X is of class at most two; and
2.	if the class is exactly 2, then 2pe = (2s + 1) 2 + 1 for some natural number s, and the degrees of basic digraphs of X are 1, s( 2s +1), (s + 1)(2s +1), and the multiplicities of the irreducible representations of X in its standard module are 1,pe,pe - 1.
Luis Martinez: Strongly regular m-Cayley circulant graphs and digraphs	201
Although this result of I. Kovacs et al. is mainly applied to the study of primitive permutation groups, it has an interpretation in terms of the kind of objects in which we are interested in this paper, because association schemes of class two are DSRGs, so that they proved that non-trivial primitive bicirculant schemes of certain orders are in fact DSRGs, and they obtained additional restrictions on that orders.
4 Uniform partial sum families
Uniform partial sum families were introduced in [2] as a kind of digraphs which generalizes what happens in family 4 of Proposition 3.2 and in part 2 of Proposition 2.3.
Definition 4.1. Let H be a group of order n > 2 and let m > 1 be an integer. Then an (m,n,k,p,X,t)-partial sum family S = {Sj, with 0 < i,j < m, of subsets of H is uniform if it satisfies the following conditions:
1.	The cardinalities of the 'diagonal' blocks Si,i are all equal.
2.	The cardinalities of the 'non-diagonal' blocks Sij, it j, are all equal.
3.	The 'diagonal' blocks {Siji : i e Zm} form a partition of H - {0}, where 0 is the identity element of the group.
The following two propositions give infinite families, found in [2], of uniform PSFs:
Proposition 4.2. If H is a group of order ef +1 and A0,..., Ae_ i is a partition of H- {0} and lA^ = f for every i, then S = {Sij}, where S^- = Aj, is a uniform (e, ef + 1,ef,f,f-1,/)-PSFin H.
Proposition 4.3. If H is a group of order ef +1 and A0,..., Ae_ 1 is a partition of H- {0} with lA^ = f for every i, then S = {Si j, where
Si,j —
Ai	if i=j,
ij l{0} uAj otherwise,
is a uniform (e, ef + 1, e(f + 1) - 1, ^	2, e + f - 1) -PSF in H.
We let A = |S0,01, and B = |S0j11. Thus,	A for every i, and ISj = B for every
distinct i and j.
Lemma 4.4. ^ (2k~p± A)/(2m) and A = k + m)B. Proof. Using the second part of Definition 3.1 we obtain
A + {m~ 1) B = k,
and applying the trivial character in the third part of the same definition with i 0, j 1 we obtain
2AB + (m- 2)B2 = /3B + pn. Using (1.1) with the DSRG associated to the PSF we get
k(k — fl) = pmn + j.
Now, the result follows from the three previous identities and the definition of A. □
202
Ars Math. Contemp. 8 (2015) 215-223
5 Form of the parameters
Now we will derive the parameters of uniform PSFs when the group H is cyclic. We will need first a lemma.
Lemma 5.1. Let & be a PSF in an abelian group H, and let x be a non-trivial character of H. Then,
m— 1
XI x(Sij) = m(fi - A)/2 + iA for some i € {0,..., m}.
l=0
Proof. By using Definition 3.1, we have that the matrix Ax = (x(Sij)) satisfies AX = fiAX + Ylm, and therefore its trace £mO1 x(Si,i) is the sum of m roots of the polynomial x2 - fix- j. Since those roots are 2 (fi± A), the result follows.	□
Proposition 5.2. If an m-circulant (m, n, k, ^, X,t)-uniform partial sum family exists with m > 3, then the parameters have one of the following forms:
1.
n = sm - rm + r2m + 1, k = sm + r2m - r,t = r2m — r + s.
X = rm + s + r2 — 2r - 1, ^ = s + r2
A = s - r + r2, B = s + r2 with r an integer and s a non-negative integer.
2.
/	\	O	0 0.	00 .0
2i(i— 1) mr2 -2r2m2i + 2m2r2i2 — sri — s + smri , k =
n
-2 sr2i2 - 4 sri + 2 sr2mi- 2 s + 4 m2r2i2 - 4 m2r2i + 4 smr i + s2
2m2 s	'
O O .0	0 0.	o	o
4 m2r2i2 — 4 m2r2i — 2 smr + s2 + 2 rm2s — 4 sm 2m2 s
s 2 r m 2 r mi s 2 r mi 2m2 s

2 r2 mi 2 mr2 i2 s	r i s 2 r m 2 r mi
A =-,B = —---
with r an integer, s a non-negative integer and i e {2,..., m}, and where 2m divides s.
s
sm
sm
sm
Luis Martinez: Strongly regular m-Cayley circulant graphs and digraphs	203
Proof. By the previous lemma, for every non-trivial caracter x of H it holds that
m—1
XI x(S;,;) = - A)/2 + iA for some i € {0,..., m}.
l=0
By part 3 of Definition 4.1 we have that the previous sum equals -1, and hence we deduce that
ft=((m- 2i)A-2)lm,	(5.1)
where A is a non-negative integer. Now, from the definition of A we obtain
Ai 1 Ai 1 Am 7 = -"--.	(5.2)
m2
Putting U = k -1, we deduce from (5.2) that
Ai 1 Ai 1 Am k=U+p-^-——^-(5.3)
m2
From (1.1),(5.1),(5.2) and (5.3) we get
( 2	2	2 2	2 2 \
n = f Um + m ^ 1 + pm — 2A i + mA i + A m ^ A m + A im — A i J (Um^ 1 + ^pm^ 2 Ai + Am + mAi + A2im - A2i2) /(m5p) (5.4)
Let us suppose that the plus sign holds in Lemma 4.4. Since A = (n - 1)/m, we obtain from that lemma that
mA i + m - m2A ^Um^ 1 + pm^ 2A i + A m + A2im - A2 i2 n=-^-. (5.5)
m2
From (5.4) and (5.5) we find p as
p=-1--(^m2A i + 2A2m^ 2A2i2 + 4 mAi- 4 A i- 2^ m2 + 3 m
2m2 1 m
- 2 m2 A - Um^ 2 mA + 2 Um^ m3 A i + A2i2m - A2m2i
± m((Um2 + 3 mA i + A2im^ 2 A i - A2i2 + m - 1 - m2A i)2
+ 4im2A2 (m-1)(-1 + i))1/2)	(5.6)
Since ft is an integer, i = 0 is not possible (see (5.1) and use that m > 3). Let us suppose that i 1 . Then,
U m2 — 1 + m ^ 2 A + 2 A m ^ A m2 ^ A2 + A2m
p =--2--(5.7)
m2
or
Um^ 1 + m - 2 A + 2 A m ^ A2 + A2 m
p =----. (5.8)
m2 1 m
Let us suppose that (5.7) holds. Then we get from (5.4) that n = 0, which gives a contradiction.
204
Ars Math. Contemp. 8 (2015) 215-223
Therefore, (5.8) must hold, and using this and (5.1),(5.2),(5.3) and (5.4) we obtain that the parameters are
mU (A + l)2 --	-'—,	(5.9)
ml
, Um^ A-A2+ A2m + A m
k =-7-i-,
m m l
-A2 + A2m - A + Am + Um t =-
m
ml
A =
Um^ l + 3 m - 2 A + 4 A m ^ A2 + A2m - 3 A m2 + A m3 ^ 2 m2
m2 m l
u (A + 1)2 M =-t + --^,	(5.10)
m l	m2
„ Um^ Am2 + 3 Am + 2 m + A2m^ 2A-1-A2- m2 A=-
m2 m l
Um2 l m
B =
Um2 l m 2 A 2 A m A2 A2 m
m2 m l
From (5.2), we have that m| (A + 1)2, and then we deduce from (5.9) that m - 1 |mU. Since m - 1 and m are coprime, then m - 1 |U. Now, from (5.10) we deduce that m| A + 1. Putting U = s(m -1) and A = rm -1 we obtain parameters as in part 1 of the proposition. Now, let us suppose that i > 1.
Since ^ is an integer, the square root in (5.6) is also an integer, and
-TT—1-- (^m2A i + 2A2m^ 2A2i2 + 4 mA i- 4 A i- 2 - m2 + 3 m
2m2 1 m
- 2 m2 A ^ Um^ 2 mA + 2 Um^ m3Ai + A2i2m - A2m2i ± mUm2 + 3 mAi + A2im - 2 A i - A2i2 + m - 1 - m2 A i + s))	(5.11)
where s is a non-negative integer and
U = (^4 m3A2i + 4A2im2 ^ 4 m2A2i2 + 4 m3A2i2 ^ s2 - 6 smAi - 2 sA2im + 4 sAi + 2 sA2i2 ^ 2 sm + 2 s + 2 sm2A i)(2sm2)
Hence,
(-s - 2 mA i + 2 m2 A i) (-s + 2 mA ^ 2 mA i - 2 m2 A + 2 m2A i)
M = "1/2"---2, \-~ (5.12)
sm2 1 m
or
s 2 mA 2 mA i s 2 mA i M = 1/2-2--(5.13)
Luis Martinez: Strongly regular m-Cayley circulant graphs and digraphs	205
Let us suppose that (5.12) holds. Then we get from (5.4) that n = -s/(2m (-1 + m)), and this contradicts that n must be positive.
Therefore, (5.13) must hold, and using this and (5.1),(5.2),(5.3) and (5.4) we obtain, by putting A = r, that the parameters are as in part 2 of the statement. From the form of A we deduce that m divides s, and from the form of ^ we conclude that 2 divides s. From this two facts and the expression for A we obtain that 2m divides s.
Finally, if the minus sign holds in Lemma 4.4, the parameters have the same form as when the plus sign holds by putting A r, so that r can have both positive and negative values.	□
By Proposition 4.2, m-circulant uniform PSFs as stated in part 1 of Proposition 5.2 always exist for r = 0 and, by Proposition 4.3, m-circulant uniform PSFs as stated in part 1 of Proposition 5.2 always exist for r = 1.
6 The tricirculant case
Now we will consider the case when m = 3. In this case, we will call the PSF tricirculant.
Proposition 6.1. If a tri-circulant (3, n, k, ^, X,t)-uniform partial sum family exists, then either
1.
n = 3r2 — 3r + 1 + 3s, k = 3r2 — r + 3s, ^ = r2 + s, A = r2 + r — 1 + s, t = 3r2 - r + s, A = r2 - r + s and B = r2 + s.	(6.1)
2.
n = 9r2 + 6r + 1, k = 9r2 + 10r + 2, ^ = 3r2 + 5r + 2, A = 3r2 + 4r + 1, t = 5r2 + 6r + 2, A = 3r2 + 2r and B = 3r2 + 4r + 1.	(6.2)
3.
n = 90r2 ^ 60r + 10, k = 90r2 ^ 40r + 3, ^ = 30r2 ^ 5r, A = 30r2 ^ 10r + 1, t = 80r2 ^ 40r + 6, A = 30r2 ^ 20r + 3 and B = 30r2 ^ 10r,	(6.3)
with r an integer and s a non-negative integer.
Proof. Using the same notations as in the proof of Proposition 5.2, we have 2 + 2iA = 0 (mod 3), and hence i = 1 or i = 2. If i = 1, by following the proof of that proposition, we can see that the parameters are as in (6.1). Let us suppose that i = 2. We will assume that the plus sign holds in Lemma 4.4, because when the minus sign holds, it is easy to prove that the parameters have the same form, changing the sign of r. We have from (5.11) that (9U + 2(A - 1)2)2 + 144A2 = ((9U + 2(A ^ 1)2) + s)2 for some positive integer s, and hence 2(9U + 2(A ^ 1)2)s + s2 = 144A2. Since U > 0, we deduce that s < 39 and, since 6 must divide s, then the possible values that s can take are 6,12,18,24,30,36. Now, having into account that A 1 mod 3 and the expression for n in Proposition 5.2 we have that for s = 18,36 we obtain a contradiction with the fact that n is an integer, and for
206
Ars Math. Contemp. 8 (2015) 215-223
s = 6,24 we obtain a contradiction with the fact that 3 divides n - 1. For s = 12, by putting A = 1 + 3r we obtain parameters as in part (6.2), and for s = 30, by putting A = 1 + 3u we have U = 2" +58"^7 and hence u = -2 (mod 5). Putting now u = -2 + 5r we obtain parameters as in (6.3).	□
We can eliminate some values of r in family (6.3). In the next proposition, Grobner bases are used (for definitions and results on Grobner bases, we refer the reader to [3]).
Proposition 6.2. If a tricirculant uniform PSF exists with parameters as in family (6.3) of the previous proposition, then r = 1 (mod 2).
Proof. If x is any non-trivial character of H then we obtain from Definition 3.1, by applying the character x, that
2
Ex(Si,0 x(Sj - Px(Si,j) = 0 for every i, j.	(6.4)
1=0
By putting the indeterminate Ti,j instead of xCSj and calculating a Grobner basis for the polynomials obtained from the lefthandsides in (6.4) with respect to the lexicographic order with
To,o > Ti,i > T2,2 > To,i > Ti,o > To,2 > T2,o > Ti,2 > T2,i > r, we conclude that
x(SM)2 ^ x(SM) - 6 + 35r + XSi,^x^2,i) - 50r2 + x(So,i)x(Si,o) + 5x(SM)r = 0.	(6.5)
Now we take the character x that takes the generator of the cyclic group H to 0n2, where 0 is a primitive n-th root of unity. Since A is an odd number and B is an even number, we have that the xC^i^) are integer numbers such that x(Si,j) is odd if i = j and even in other case. Now, we obtain from (6.5) that
(x(Si,i) - 1)(x(Si,i) +r) = 2(r2 + 1) (mod 4).
Suppose that r is even. Then the above implies that x^m) = 3 (mod 4). We show below that this leads to a contradiction, hence r must be indeed odd.
By the choice of the character x we get for every i e {0,1,2},
x(Si,i) = -|Si,i| + 2|SM n ker(x)l = -30r^ 20r ^ 3 + 2|SM n ker(x)|.
The group ker(x) is of order n/2 = 45r2 - 30r + 5, which is odd. Using this and that u?=o(S^ n ker(x)) = ker(x) - {0}, we see that at least one of the numbers |Si,^ ker(x)| must be even. We may set the indices at the beginning so that Si, i ker x is even, and hence above we find x(Sm ) = 1 (mod 4), a contradiction.	□
Apart from the infinite families of uniform PSFs showed in Section 4, we will analyze some sporadic examples for the tricirculant case.
When s = 0 in the first family in Proposition 6.1, that is, when the graph is undirected, Kutnar et al. found in [16] PSFs for r = 1,2 and 3.
Luis Martinez: Strongly regular m-Cayley circulant graphs and digraphs	207
For r = -1, s = 2, a PSF with the parameters and structure indicated in Proposition 6.1 was found by the author and A. Araluze in [20].
We have found now for r = 2, s = 2, by using techniques of combinatorial optimization, a uniform tricirculant PSF which generates a DSRG with new parameters, which appear as an undecided case in Hobart and Brouwer's table [10]. This PSF is
S0,0 = (3,4,7, 9), S0,i = (0,4, 7, 8,11,12), S0,2 = (0,1,2,4,6,10),
Si,o = (1, 2,5, 6, 8, 9), SM = (1, 5,6,12), S1,2 = (2, 3,5, 6,7, 8),
S2,0 = (0,1, 3, 7, 9,11), S2^ = (0, 5, 6,7, 8,11), S2,2 = (2,8,10,11). 7 Almost-uniform partial sum families
In this section we will present a kind of partial sum families that generalizes the uniform ones.
Definition 7.1. Let H be a group of order n > 2, H' a subgroup of H of order n' and let m > 1 be an integer. Then an (m, n, k, A, t) -partial sum family S = {Sj, with 0 < i, j < m, with the S^ subsets of H, is almost-uniform with respect to H' if it satisfies the following conditions:
1.	The cardinalities of the 'diagonal' blocks Sj,j are all equal.
2.	The cardinalities of the 'non-diagonal' blocks Sjj, it j, are all equal.
3.	The'diagonal'blocks {S^ : ie Zm} form a partition of H-H'.
Remark 7.2. Observe that in the particular case when H' = {e} almost uniform PSFs are just uniform PSFs. In what follows, we will study the case when H' is a proper subgroup of H.
Let us analyze the form of the parameters of m-circulant (m,n, k,^, A,i)-almost-uniform partial sum families over a cyclic group H with respect to a proper and non-trivial subgroup H :
Proposition 7.3. If an (m, n, k, A, i)-almost-uniform partial sum family exists with m > 3 with respect to a proper and non-trivial subgroup H' of the cyclic group H, then the parameters have one of the following forms:
1.
n = (im — m + i) imr2 + (1 — i) mr + ms, k = (im — m + i) imr^ (^ + m — im) r + ms, ^ = (im — m + ^ ir^ ri + s,
A = (¿m — m + ^ ¿r^ (m — 3 i) r + s,
163
Ars Math. Contemp. 8 (2015) 215-223
t = —ri + i2 r2 m + s. A = (im - m + i) ir2 + (1^2 i)r + s. and B = {im — m + i) ir2 + (1 — i)r + s.
r2j2
= (j ~ j) r + ( —j — 1) r + sr '
m
,(■2^2-, , 1 + rj)
k = (j ^j)r -rj + sml--.
m
rj rj m rm rj m
p = s ■
, rj( m — r^ + rjm + rj) X = s + r H-------.

rj (rmj — 2 m - mr + rj ) A — s + ---.
rj (—m — mr + rmj + rj)
where m divides rj.
3.
2p (p — 1) mr2 r Í2r m2p - 2rm2p2 + si + sp- smp) -. k =--.
/ 2 • 2'2 2 2 22 22 222 t = —(^2 sr mi + 2 sr i + 4 sr ip - 2 sr mp + 2 sr p + 4 m r p - 4 m r p
+ 2 srm — 4 srmp - s2)/(2m2s).
0 0	000	o	o
4 m2r2p — 4 r2m2p2 + 2 srm — s— 2 rm2 s + 4 srmi
X = ^v2--.
(s + 2rmp){s- 2rm + 2rmp) M = 1/2-2-.
r(^2 mrp2 + 2 mrp + si) rp(s- 2 mr + 2 mrp) A =--. B =-.
m2
m
n
s
sm
ms
ms
Luis Martinez: Strongly regular m-Cayley circulant graphs and digraphs	209
Proof. We have Ui Si,i = H - H'. If x is a character of H which is non-trivial on H', then Si x(Si,i) = 0. If X is trivial on H' but not on H, then £i x'(Si,i) = -|H'|. Since, by Lemma 5.1, the difference of both sums of characters must be divisible by A, we have that |H'| = iA with i€ {1,..., m}. Since, again by Lemma 5.1, £; x(Si,i) = ~ A)/2+ jA with j e {0, ...m}, we have
fi=(m- 2j)A/m,	(7.1)
where A is a non-negative integer. We have
1=jm-j 2) A2/m2.	(7.2)
Now,
j=t-p= {jm-j2)A2jm2, k = U + p + {jm-j2)A2jm2(where U = k-t),
2j) Am.	(7.3)
From these equalities and (1.1) we get
2	2	2	22\/2	2
n=(Um + pm + Amj + A mj - Aj )(Um + pm + Amj
- Am2 + jA2m-j2A2)I(m5p)	(7.4)
Let us suppose that the plus sign holds in Lemma 4.4 Since the PSF is almost-uniform we have n-iA = mA, and therefore
Um2 + pm2 + A mj - j 2A2+ jA2m- A m2j + iA m2 n =-2--(7.5)
m2
From (7.4) and (7.5) we deduce
/	2 3	223	2223	2
p = (-A m - m U + mj A — m iA + 2 Um - m jA + m A j - A m j + 2 A mj - 2 j2 A2 + 2 jA2m±m((Um2 - A m - 2 A mi + iA m2 + 3 A mj -j2A2 + j A^m- A m2j) 2+ 4 m2A2( + 1) {i-j){m- 1))V2) /(2m2( m-1)).
Let us suppose that j = i. Then,
Um2 + A mi + iA2m- i2A2 P =--2--(7.6)
or
Um2 + A mi- A m2 + iA2m- i2 A2
P =-27-n--(7.7)
m2 (m~ 1;
If (7.6) holds, then we get from (7.4) that n = 0, which is a contradiction. Thus, (7.7) must hold, and we obtain
Um2 + A mi- A m + iA2m-i2 A2	(78)
; (m — 1)
210
Ars Math. Contemp. 8 (2015) 215-223
Um2 + A i- A m + iA2m-i2 A2
k=-a-^--(7.9)
m m l
iA2m - i2 A2 + Um + A i- A m t =---T---(7.10)
m m l
Um2 + 3 A mi — 2 A m2 + iA2m-i2A2 + A m3 - 2 A m2i
A =-27-n- (7.11)
m2 m l
Um2 + A mi — A m2 + iA2m-i2A2 , ,„N ^-27-n--(7.12)
m2 m l
Um2 + 2 A m^ A m + iA2m-i2 A2 - A m2i
^-m-n--(7.13)
m2 m l
„ Um2 + Ami - Am + iA2m-i2A2 B =-—,-^--(7.14)
m2 m l
From (7.12) we have i2 A2 = 0 (mod m) and, from (7.9), -i2 A2 + ¿^0 (mod m). Therefore, i^0 (mod m).
From (7.13), (im- i2)A2 + (2i - 1)mA = 0 (mod m2). Using this and the previous congruence, we obtain mA = 0 (mod m2), and hence
A = 0 (mod m).	(7.15)
From (7.12),
U=(i2^ i)A2 + (1- i)A (mod m- 1).	(7.16) Now, using the two previous congruences and putting
A = rm and U = i(i — 1)r2m2 + (1 — i)rm + s(m~ 1),
we obtain parameters as in part 1 of the proposition. Now, let us suppose that j = i + 1.
In this case, by reasoning in a similar way as before, we obtain
Um2 - A m2 + j A2m + A m + A mj - j2 A2 , , n =-7-T\--(7.17)
m m 1
Um2 + j A + jA2m — j2 A2 k=-j . j ^ j--(7.18)
m m 1
Um2	mj j 2m j2 2
M=--rr--(7.19)
m2 m 1
Um2 3 mj j 2m j2 2 m2 m3 2 m2j
* = -2H-T\- (7.20)
m2 m 1 j 2m j2 2 Um j
t= j--U-—	(7.21)
m m 1
Luis Martinez: Strongly regular m-Cayley circulant graphs and digraphs	211
Um2 + jA2m + 2 A mj-j2A2 - A m2j A =	^ 7\	(7.22)
m2 (m — 1)
Um^ A mj+jA2m^j2A2 B =-^-T\--(7.23)
m2 m 1
From (7.19) we have A2j2 = 0 (mod m), and from (7.18), Aj - A2j2 = 0 (mod m), and hence A j s 0 (mod m).
From (7.19), we have U + Aj + A2j ^ A2j2 = 0 (mod m - 1). Putting U = -Aj - A2j + A2j2 + s(m - 1) and A = r, we obtain parameters as in part 2 of the proposition.
When j f i and j ^ i + 1 we find the parameters following the line of the proof of Proposition 5.2 and putting p = j - i and r = A.
If the minus sign holds in Lemma 4.4, we find analogous families of parameters by putting r = -A, so that r can be positive or negative.	□
We have found, by using methods of combinatorial optimization, 14 examples of PSFs corresponding to family 1, which are listed in the appendix. For three of the examples, corresponding to m = 3, i = 1, r = -1, s = 3, m = 3, i = 1, r = -1, s = 4 and to m = 5, i = 1,r = 1, s = 2, the parameters appear as undecided cases in Hobart and Brouwer's table [10]. We wonder if such PSFs exist for m = 3, i = 1, r = 1 or r = and every positive integer s.
8 Appendix
Family 1: For m = 3:
1.	i 1, r 1, s 1:
(((1), (0,1, 5), (2, 3,5)),(( 0, 3,5),( 3), (0,1,4)), ((1, 3,4),( 0,1, 2),( 5)))
2.	i = 1,r = -1,s = 2:
(((5,8), (0,4, 6, 7), (0,1,3, 7)), (( 1,2, 3, 5), (2,4), (0, 5, 6, 7)), ((2, 3,6, 8), (0, 3,4,7),( 1,7)))
3.	i = 1, r = —1, s = 3:
(((5,9,11),( 1,2,4,9,10),(0,1, 3, 8,9)), ((3, 5,8, 9,11), (1, 2,10), (0,1, 3, 7, 9)), ((0, 2,3,4,11), (4, 5,7, 8, 9), (3, 6,7)))
4.	i 1 , r 1 , s 4:
(((6,9,12,13), (0,1, 3,4,11,12), (6, 7,10,11,13,14)), ((1,4,5, 8,10,14), ( 1, 7,11,14), (0, 2, 5, 6,9,11)), ((1, 2,3,4,7, 9), (0,7, 8,9,10,13), (2,3,4,8)))
5.	i 1 , r 1 , s 1 :
(((5), (3,4), (2,3)),((2, 3), (1),(0,5)),((0, 3), (1,4),(3)))
212
Ars Math. Contemp. 8 (2015) 215-223
6.	i = 1, r = 1, s = 2:
(((7, 8), (0,1, 2), (2,3, 4)), ((3, 7, 8), (1, 5), (2, 3, 7)), ((0, 5, 7),(0,2, 7), (2,4)))
7.	i = 1, r = 1, s = 3:
(((3, 9,10), (0,5, 6,7), (6, 7, 8, 9)), ((0, 3, 9,10), (5, 6,7), (6,7, 8, 9)), ((2, 3, 5, 8), (0, 5,10,11), (1, 2,11)))
8.	i = 1,r = 1, s = 4:
(((6, 8,12,14), (3, 5, 9,11,12), (5,7,11,13,14)), ((1, 3,4, 5,7), (1, 2,4,13), (0, 2, 3,4, 6)), ((1,4, 8,10,12), (1, 5, 7, 9,13), (3,7, 9,11)))
For m 4:
1.	i 1, r 1, s 1:
(((4, 6, 7), (4, 5), (4,7), (0,1)), ((3,4), (1, 2,4), (4, 5), (1, 6)), ((1,4), (2, 3), (4, 5, 6), (2, 3)), ((0,1), (2,7), (5, 6), (2, 3,4)))
2.	i 1 , r 1 , s 1 :
(((5), (4, 7), (3, 6), (4,7)), (( 1, 2), (1), (0, 7), (0, 1)), ((1, 2), (0,1), (7), (0,1)), ((1,4), (0,3), (2, 7), (3)))
3.	i= 1,r = 1,s = 2:
(((1, 2),(3,4, 5), (4,5, 6), (2, 6,10)), ((2,4, 9),(5,7),(1, 6,8),(2,6,10)), ((6, 7, 8),(9,10,11) ,( 10,11) ,( 0,4, 8)), ((0, 2, 7) ,( 3,5,10) ,( 4,6,11),(4, 8)))
4.	i 1 , r 1, s 3:
(((3,13,14), (8,9,10,11), (1,2, 3,12), (0, 9,10,11)), ((4, 5, 7,10), (1,2,15), (3,8, 9,10), (0,1,2, 7)), ((1, 2,4, 7), (12,13,14,15), (5,6, 7), (4,13,14,15)), ((0, 3,13,14), (8,9,10,11), (1,2, 3,12), (9,10,11)))
For m 5:
1.	i 1, r 1, s 1:
(((5), (0, 7), (1, 2), (6,7), (3, 6)), ((3, 8), (3), (4, 5), (0, 9), (6,9)), ((4, 9), (6, 9), , (5, 6), (2, 5)), ((3,8), (0, 3), (4, 5), (9), (6, 9)), ((4, 9), (1,4), (5, 6),(0,1),(7)))
2.	i= 1,r = 1,s = 2:
(((2,13), (0, 2,4), (7,9,11), (0,2, 4), ( 10,12,14)), ((3,13,14), (1, 5), (7, 8,12), (0,1, 5), (0,10,11)), ((1, 5, 6), (3,7, 8), (10,14), (3, 7, 8), (2, 3,13)), ((2, 6,13), (0,4,8), (0,7,11), (4, 8), (3,10,14)), ((3,10,14), (1, 5,12), (4, 8,12), (1, 5,12), (7,11)))
Acknowledgments: The author thanks the anonymous reviewers for their valuable suggestions and comments.
Luis Martinez: Strongly regular m-Cayley circulant graphs and digraphs	213
References
[1]	A. Araluze, K. Kutnar, L. Martinez and D. Marusic, Edge Connectivity in Difference Graphs and some new constructions of Partial Sum Families, European J. Combin. 32 (2011), 352-360.
[2]	A. Araluze, I. Kovacs, K. Kutnar, L. Martinez, D. Marusic, Partial sum quadruples and bi-Abelian digraphs, J. Combin. Theory Ser. A 119 (2012), 1811-1831.
[3]	T. Becker, V. Weispfenning and H. Kredel, Grobner bases, a computational approach to commutative algebra, Graduate texts in mathematics, vol. 141, Springer, New York (1993).
[4]	R. C. Bose, Strongly regular graphs, partial geometries and partially balanced designs, Pacific J. Math. 13 (1963), 389-419.
[5]	W. G. Bridges and R. A. Mena, Rational circulants with rational spectra and cyclic strongly regular graphs, Ars Combin. 8 (1979), 143-161.
[6]	A. Duval, A directed graph version of strongly regular graphs, J. Combin. Theory Ser. A 47 (1988), 71-100.
[7]	A. Duval and D. Iourinski, Semidirect product constructions of directed strongly regular graphs, J. Combin. Theory Ser. A 104 (2003), 157-167.
[8]	F. Fiedler, M. H. Klin and M. Muzychuk, Small vertex-transitive directed strongly regular graphs, Discrete Math. 255 (2002), 87-115.
[9]	S. A. Hobart and T. J. Shaw, A note on a family of directed strongly regular graphs, European J. Combin. 20 (1999), 819-820.
[10]	S. A. Hobart, Parameters of directed strongly regular graphs, http://homepages.cwi. nl/\textasciitildeaeb/math/dsrg/dsrg.html
[11]	L. K. J0rgensen, Directed strongly regular graphs with ^ = a, Discrete Math. 231 (2001), 289-293.
[12]	L. K. J0rgensen, Non-existence of directed strongly regular graphs, Discrete Math. 264 (2003), 111-126.
[13]	L. K. J0rgensen, Rank of adjacency matrices of directed (strongly) regular graphs, Linear Algebra Appl. 407 (2005), 233-241.
[14]	M. Klin, A. Munemasa, M. Muzychuk and P. -H. Zieschang, Directed strongly regular graphs obtained from coherent algebras, Linear Algebra Appl. 377 (2004), 83-109.
[15]	I. Kovaics, D. Marussics, M. Muzychuk, Primitive bicirculant association schemes and a generalization of Wielandt's theorem, Trans. Amer. Math. Soc. 362 (2010), 3203-3221.
[16]	K. Kutnar, D. Marusic, S. Miklavic, P. Sparl, Strongly regular tri-Cayley graphs, European J. Combin. 30 (2009), 822-832.
[17]	K.H. Leung, S.L.Ma, Partial difference triples, J. Algebraic Combin. 2 (1993), 397-409.
[18]	A. Malnic, D. Marusic, P. Sparl and B. Frelih, Symmetry structure of bicirculants, Discrete Math. 307 (2007), 409-414.
[19]	A. Malnic, D. Marusic and P. Sparl, On strongly regular bicirculants, European J. Combin. 28 (2007), 891-900.
[20]	L. Martinez and A. Araluze, New tools for the construction of directed strongly regular graphs: difference digraphs and partial sum families, J. Combin. Theory Ser. B 100 (2010), 720-728.
[21]	D. Marusic, Strongly regular bicirculants and tricirculants, Ars Combin. 25 C (1988), 11-15.
[22]	M. J. de Resmini and D. Jungnickel, Strongly regular semi-Cayley graphs, J. Algebraic Combin. 1 (1992), 171-195.