The Moore Graph of Diameter 2 and Degree 57 via Cyclic Derangements
Open Access
Abstract
The possible existence of a regular Moore graph of diameter 2 and degree 57 with the maximum number 3250 of vertices has been an open question for over 65 years. One approach to a construction focuses on the set of permutations that describe the 1-factors that give the adjacencies between leaf vertices of pairs of branches of a tree. Most of these permutations are derangements, that is they are permutations with no fixed points. As many products of 2, 3, or 4 of these derangements must also be derangements, it is tempting to use a group of derangements, that is a group of permutations in which every non-identity element is a derangement. The first case to consider is when the group of derangements is a cyclic group of permutations. In this paper it is proved that a construction using only a cyclic group of permutations is impossible. This leaves only the possibility of using some other group of derangements, or a set of derangements that do not form a group. The prospects for extending the work to these cases is considered at the end of the paper.Keywords
This publication has 9 references indexed in Scilit:
- Potential Subgraphs of the Missing Moore GraphSymmetry, 2024
- The missing Moore graph as an optimization problemEURO Journal on Computational Optimization, 2023
- A survey on the missing Moore graphLinear Algebra and its Applications, 2019
- Search for properties of the missing Moore graphLinear Algebra and its Applications, 2010
- The number of transversals in a Latin squareDesigns, Codes and Cryptography, 2006
- Automorphisms of Aschbacher GraphsAlgebra and Logic, 2001
- Algebraic Graph Theory1974
- The nonexistence of rank three permutation groups of degree 3250 and subdegree 57Journal of Algebra, 1971
- On Moore Graphs with Diameters 2 and 3IBM Journal of Research and Development, 1960