Allan van Hulst: The quest for the mythical 57-regular Moore graph

Event Details

Since 1966 it is known that only four regular undirected graphs having diameter 2 and girth 5 can exist. The construction of three of these 5,2-Moore graphs is known but it is still an open problem whether the remaining candidate srg(3250,57,0,1) exists at all. I have developed an algorithm that constructs a partial solution to this problem. In particular, I was able to remove all 3-cycles and 2 of the 3 types of 4-cycles from an initial 57-regular graph of order 3250. During this talk, I would like to tap into possible algorithmic insights of members of the group to try and see whether anyone has any ideas concerning removal of the remaining 4-cycles. I will also discuss a number of earlier findings in previous research. Notably, and contrary to the other 5,2-Moore graphs, this graph cannot be vertex-transitive and the order of its automorphism group is quite small (at most 375).