Abstract
In this paper, we give a construction of strongly regular Cayley graphs and a construction of skew Hadamard difference sets. Both constructions are based on choosing cyclotomic classes of finite fields, and they generalize the constructions given by Feng and Xiang [10,12]. Three infinite families of strongly regular graphs with new parameters are obtained. The main tools that we employed are index 2 Gauss sums, instead of cyclotomic numbers.
Similar content being viewed by others
References
B. Berndt, R. Evans and K. S. Williams: Gauss and Jacobi Sums, Wiley, 1997.
T. Beth, D. Jungnickel and H. Lenz: Design Theory. Vol. I. Second edition, Encyclopedia of Mathematics and its Applications, 78. Cambridge University Press, Cambridge, 1999.
L. D. Baumert, J. Mykkeltveit: Weight distributions of some irreducible cyclic codes, DSN Progr. Rep., 16 (1973), 128–131.
L. D. Baumert, W. H. Mills, R. L. Ward: Uniform cyclotomy, J. Number Theory 14 (1982), 67–82.
A. E. Brouwer, W. H. Haemers: Spectra of Graphs, Springer, Universitext, 2012.
A. E. Brouwer, R. M. Wilson and Q. Xiang: Cyclotomy and strongly regular graphs, J. Alg. Combin. 10 (1999), 25–28.
R. Calderbank and W. M. Kantor: The geometry of two-weight codes, Bull. London Math. Soc. 18 (1986), 97–122.
E. R. van Dam: A characterization of association schemes from affne spaces, Des. Codes Cryptogr. 21 (2000), 83–86.
E. R. van Dam: Strongly regular decompositions of the complete graphs, J. Alg. Combin. 17 (2003), 181–201.
T. Feng and Q. Xiang: Strongly regular graphs from union of cyclotomic classes, J. Combin. Theory (B) 102 (2012), 982–995.
T. Feng, F. Wu and Q. Xiang: Pseudocyclic and non-amorphic fusion schemes of the cyclotomic association schemes, Designs, Codes and Cryptography 65 (2012), 247–257.
T. Feng and Q. Xiang: Cyclotomic constructions of skew Hadamard difference sets, J. Combin. Theory (A) 119 (2012), 245–256.
C. Godsil and G. Royle: Algebraic Graph Theory GTM 207, Springer-Verlag, 2001.
M. Hall: A survey of difference sets, Proc. Amer. Math. Soc. 7 (1956), 975–986.
T. Ikuta and A. Munemasa: Pseudocyclic association schemes and strongly regular graphs, Europ. J. Combin. 31 (2010), 1513–1519.
A. A. Ivanov, C. E. Praeger: Problem session at ALCOM-91, Europ. J. Combin. 15 (1994), 105–112.
E. S. Lander: Symmetric designs: an algebraic approach, Cambridge University Press, 1983.
R. Lidl and H. Niederreiter: Finite Fields, Cambridge University Press, 1997.
P. Langevin: Calcus de certaines sommes de Gauss, J. Number Theory 63 (1997), 59–64.
C. L. M. de Lange: Some new cyclotomic strongly regular graphs, J. Alg. Combin. 4 (1995), 329–330.
J. H. van Lint and A. Schrijver: Construction of strongly regular graphs, two-weight codes and partial geometries by finite fields, Combinatorica 1 (1981), 63–73.
S. L. Ma: A survey of partial difference sets, Des. Codes Cryptogr. 4 (1994), 221–261.
O. D. Mbodj: Quadratic Gauss sums, Finite Fields Appl. 4 (1998), 347–361.
P. Meijer, M. van der Vlugt: The evaluation of Gauss sums for characters of 2-power order, J. Number Theory 100 (2003), 381–395.
T. Storer: Cyclotomy and Difference Sets, Lectures in Advanced Mathematics, Markham Publishing Company, 1967.
R. J. Turyn: Character sums and difference sets, Pacific J. Math. 15 (1965), 319–346.
J. Yang and L. Xia: Complete solving of explicit evaluation of Gauss sums in the index 2 case, Sci. China Ser. A 53 (2010), 2525–2542.
J. Yang and L. Xia: A note on the sign (unit root) ambiguities of Gauss sums in the index 2 and 4 case, preprint, arXiv:0912.pp1414v1.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Feng, T., Momihara, K. & Xiang, Q. Constructions of strongly regular Cayley graphs and skew Hadamard difference sets from cyclotomic classes. Combinatorica 35, 413–434 (2015). https://doi.org/10.1007/s00493-014-2895-8
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00493-014-2895-8