×

New mixed Moore graphs and directed strongly regular graphs. (English) Zbl 1371.05322

Summary: A directed strongly regular graph with parameters \((n, k, t, \lambda, \mu)\) is a \(k\)-regular directed graph with \(n\) vertices satisfying that the number of walks of length 2 from a vertex \(x\) to a vertex \(y\) is \(t\) if \(x = y\), \(\lambda\) if there is an edge directed from \(x\) to \(y\) and \(\mu\) otherwise. If \(\lambda = 0\) and \(\mu = 1\) then we say that it is a mixed Moore graph. It is known that there are unique mixed Moore graphs with parameters \((k^2 + k, k, 1, 0, 1)\), \(k \geq 2\), and \((18, 4, 3, 0, 1)\). We construct a new mixed Moore graph with parameters \((108, 10, 3, 0, 1)\) and also new directed strongly regular graphs with parameters \((36, 10, 5, 2, 3)\) and \((96, 13, 5, 0, 2)\). This new graph on 108 vertices can also be seen as an example of a so called multipartite Moore digraph. Finally we consider the possibility that mixed Moore graphs with other parameters could exist, in particular the first open case which is \((40, 6, 3, 0, 1)\).

MSC:

05E30 Association schemes, strongly regular graphs

Software:

GAP; GRAPE; nauty
Full Text: DOI

References:

[1] Bosák, J., Partially directed Moore graphs, Math. Slovaca, 29, 181-196 (1979) · Zbl 0407.05057
[2] Brouwer, A. E., Strongly regular graphs, (Colbourn, C. J.; Dinitz, J. H., Handbook of Combinatorial Designs (2006), Chapman & Hall), 852-867
[3] Brouwer, A. E.; Cohen, A. M.; Neumaier, A., Distance-regular Graphs (1989), Springer-Verlag: Springer-Verlag Berlin · Zbl 0747.05073
[4] Dixon, J. D.; Mortimer, B., Permutation Groups (1996), Springer · Zbl 0951.20001
[5] Duval, A. M., A Directed version of strongly regular graphs, J. Combin. Theory Ser. A, 47, 71-100 (1988) · Zbl 0642.05025
[6] Fiol, M. A.; Gimbert, J.; Miller, M., Multipartite Moore digraphs, Linear Algebra Appl., 419, 234-250 (2006) · Zbl 1105.05028
[8] Gimbert, J., Enumeration of almost Moore digraphs of diameter two, Discrete Math., 231, 177-190 (2001) · Zbl 0979.05059
[9] Jørgensen, L. K., Directed strongly regular graphs with \(\mu = \lambda \), Discrete Math., 231, 289-293 (2001) · Zbl 0979.05114
[10] Jørgensen, L. K., Adjacency matrices of some directed strongly regular graphs · Zbl 1074.05060
[11] Klin, M.; Munemasa, A.; Muzychuk, M.; Zieschang, P.-H., Directed strongly regular graphs obtained from coherent algebras, Linear Algebra Appl., 377, 83-109 (2004) · Zbl 1030.05119
[12] López, N.; Pujolàs, J., Properties of mixed Moore graphs of directed degree one, Discrete Math., 338, 522-526 (2015) · Zbl 1305.05239
[13] Lyubshin, D. S.; Savchenko, S. V., Cayley digraphs with normal adjacency matrices, Discrete Math., 309, 4343-4348 (2009) · Zbl 1179.05053
[14] McKay, B. D., Nauty User’s Guide (version 1.5), Technical Report TR-CS-90-02 (1990), Australian National University, Computer Science Department: Australian National University, Computer Science Department ANU
[15] Nguyen, M. H.; Miller, M.; Gimbert, J., On mixed Moore graphs, Discrete Math., 307, 964-970 (2007) · Zbl 1112.05031
[16] O’Keefe, M.; Wong, P. K., The smallest graph of girth 6 and valency 7, J. Graph Theory, 5, 79-85 (1981) · Zbl 0448.05041
[17] Soicher, L. H., GRAPE: a system for computing with graphs and groups, (Finkelstein; Kantor, Groups and Computation. Groups and Computation, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 11 (1993), American Mathematical Society), 287-291 · Zbl 0833.05071
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.