×

zbMATH — the first resource for mathematics

Directed strongly regular graphs obtained from coherent algebras. (English) Zbl 1030.05119
Summary: The notion of a directed strongly regular graph was introduced by A. M. Duval [J. Comb. Theory, Ser. A 47, 71-100 (1988; Zbl 0642.05025)] as one of the possible generalizations of classical strongly regular graphs to the directed case. We investigate this generalization with the aid of coherent algebras in the sense of D. G. Higman. We show that the coherent algebra of a mixed directed strongly regular graph is a non-commutative algebra of rank at least 6. With this in mind, we examine the group algebras of dihedral groups, the flag algebras of a Steiner 2-designs, in search of directed strongly regular graphs. As a result, a few new infinite series of directed strongly regular graphs are constructed. In particular, this provides a positive answer to a question of Duval on the existence of a graph with certain parameter set having 20 vertices. One more open case with 14 vertices listed in Duval’s paper is ruled out, while new interpretations in terms of coherent algebras are given for many of Duval’s results.

MSC:
05E30 Association schemes, strongly regular graphs
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05B05 Combinatorial aspects of block designs
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
Citations:
Zbl 0642.05025
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bannai, E.; Ito, T., Algebraic combinatorics I. association schemes, (1984), Benjamin/Cummings Menlo Park, CA · Zbl 0555.05019
[2] Bose, R.C., Strongly regular graphs, partial geometries and partially balanced designs, Pacific J. math., 13, 389-419, (1963) · Zbl 0118.33903
[3] Brown, E.; Reid, K.B., Doubly regular tournaments are equivalent to skew-Hadamard matrices, J. combin. theory ser. A, 12, 332-338, (1972) · Zbl 0236.05109
[4] Brouwer, A.E.; van Lint, J.H., Strongly regular graphs and partial geometries, (), 85-122 · Zbl 0555.05016
[5] Duval, A.M., A directed version of strongly regular graphs, J. combin. theory ser. A, 47, 71-100, (1988) · Zbl 0642.05025
[6] Faradjev, I.A., Constructive enumeration of combinatorial objects, In: problèmes combinatoiree et thèorie des graphs, Coll. int. CNRS. Paris, 260, 131-135, (1988)
[7] (), in Russian
[8] Faradžev, I.A.; Ivanov, A.A.; Klin, M.H., Galois correspondence between permutation groups and cellular rings (association schemes), Graphs combin., 6, 303-332, (1990) · Zbl 0764.05099
[9] Faradžev, I.A.; Klin, M.H.; Muzichuk, M.E., Cellular rings and groups of automorphisms of graphs, (), 1-152 · Zbl 0795.05073
[10] Feit, W.; Higman, G., The non-existence of certain generalised polygons, J. algebra, 1, 114-131, (1964) · Zbl 0126.05303
[11] Fiedler, F.; Klin, M.; Pech, C., Directed strongly regular graphs as elements of coherent algebras, (), 69-87
[12] Godsil, C.D., Algebraic combinatorics, (1993), Chapman & Hall NY · Zbl 0814.05075
[13] Ja.Ja. Gol’fand, A description of subrings in V(Sp1×Sp2×⋯×Spk), in: M.H. Klin, I.A. Faradžev (Eds.), Investigation in Algebraic Theory of Combinatorial Objects, Moscow, VNIISI, 1985, pp. 65-76 (Russian)
[14] Gorenstein, D., Finite simple groups. an introduction to their classification, (1982), Plenum Press NY · Zbl 0483.20008
[15] Hestenes, M.D.; Higman, D.G., Rank 3 groups and strongly regular graphs, SIAM-AMS proc., providence, 4, 141-160, (1971) · Zbl 0253.05127
[16] Higman, D.G., Finite permutation groups of rank 3, Math. Z., 86, 145-156, (1964) · Zbl 0122.03205
[17] Higman, D.G., Coherent configurations I, Rend. sem. mat. univ. Padova, 44, 1-25, (1970) · Zbl 0279.05025
[18] Higman, D.G., Coherent configurations. part I: ordinary representation theory, Geom. dedicata, 4, 1-32, (1975) · Zbl 0333.05010
[19] Higman, D.G., Coherent algebras, Linear algebra appl., 93, 209-239, (1987) · Zbl 0618.05014
[20] Higman, D.G., Computations related to coherent configurations, Congr. numer., 75, 9-20, (1990) · Zbl 0737.05077
[21] Hobart, S.A.; Shaw, T.J., A note on a family of directed strongly regular graphs, European J. combin., 20, 77-90, (1999)
[22] Hoffman, A.J., On the polynomial of a graph, Amer. math. monthly, 70, 30-36, (1963) · Zbl 0112.14901
[23] Hubaut, X.L., Strongly regular graphs, Discrete math., 4, 357-381, (1975) · Zbl 0311.05122
[24] Iwahori, N., On the structure of a Hecke ring of a Chevalley group over a finite field, J. fac. sci. univ. Tokyo. sect 1A math., 10, 215-236, (1964) · Zbl 0135.07101
[25] Jørgensen, L.K., Non-existence of directed strongly regular graphs, Discrete math., 264, 111-126, (2003) · Zbl 1014.05074
[26] Jungnickel, D., Difference sets, (), 241-324 · Zbl 0768.05013
[27] Kilmoyer, R.; Solomon, L., On the theorem of feit – higman, J. combin. theory ser. A, 15, 310-322, (1973) · Zbl 0279.20009
[28] Klin, M., On classical and directed versions of strongly regular graphs, Mathematisches forschungsinstitut oberwolfach. tagungsbericht, 2, 6, (1994)
[29] M. Klin, A. Munemasa, M. Muzychuk, P.-H. Zieschang, Directed strongly regular graphs via coherent (cellular) algebras, Preprint, Kyushu - MPS - 1997 - 12, Kyushu University, Fukuoka, Japan, 1997, p. 57
[30] M. Klin, Ch. Pech, P.-H. Zieschang, Flag algebras of block designs. I. Initial notions. Steiner 2-designs and generalized quadrangles, Preprint, MATH - AL - 10 - 1998, Technische Universität Dresden, November 1998, p. 47
[31] Ledermann, W., Introduction to group characters, (1987), Cambridge University Press Cambridge · Zbl 0625.20003
[32] Liebeck, M.W.; Saxl, J., The finite primitive permutation groups of rank three, Bull. London math. soc., 18, 165-172, (1986) · Zbl 0586.20003
[33] Liebler, R.A., Tactical configurations and their generic rings, European J. combin., 9, 581-592, (1988) · Zbl 0664.05013
[34] Ott, U., Bericht über Hecke algebren und Coxeter algebren endlicher geometrien, London math. soc. lect. notes ser., 49, 260-271, (1981) · Zbl 0471.05017
[35] Ott, U., On finite geometries of type B3, J. combin. theory ser. A, 39, 209-221, (1985) · Zbl 0573.51003
[36] Scott, W.R., Group theory, (1964), Prentice-Hall Englewood Cliffs · Zbl 0126.04504
[37] Seidel, J.J., Strongly regular graphs of L2-type and of triangular type, Indag. math., 29, 188-196, (1967) · Zbl 0161.20802
[38] Shiu, W.C., Schur rings over dihedral groups, Chinese J. math., 18, 209-223, (1990) · Zbl 0745.20006
[39] Smith, K.W., Flag algebras of a symmetric design, J. combin. theory ser. A, 48, 209-228, (1988) · Zbl 0684.05007
[40] O. Tamaschke, Schur-Ringe, Bibliogr. Inst. Mannheim, 1970
[41] Wielandt, H., Zur theorie der einfach transitiven permutationsgruppen II, Math. Z., 52, 384-393, (1949) · Zbl 0034.01601
[42] ()
[43] Weisfeiler, B.Ju.; Leman, A.A., A reduction of a graph to a canonical form and an algebra arising during this reduction, Nauchno-technicheskaya informatsia, ser. 2, 9, 12-16, (1968), in Russian
[44] Zieschang, P.-H., Homogeneous coherent configuration as generalized groups and their relationship to buildings, J. algebra, 178, 667-709, (1995)
[45] Zieschang, P.-H., ()
[46] Zieschang, P.-H., On dihedral configurations and their Coxeter geometries, European J. combin., 18, 362-375, (1997)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.