Skip to content

michaelmathen/Moore

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

18 Commits
 
 
 
 
 
 
 
 

Repository files navigation

This project attempts to find all of the Moore Graphs with girth 5. 
According to Wikipedia:
The Hoffman–Singleton theorem states that any Moore graph with girth 5 must have degree 2, 3, 7, or 57. The Moore graphs are:
   The complete graphs  K_n  on n > 2 nodes. (diameter 1, girth 3, degree n-1, order n)
   The odd cycles  C_{2n+1} . (diameter n, girth 2n+1, degree 2, order 2n+1)
   The Petersen graph. (diameter 2, girth 5, degree 3, order 10)
   The Hoffman–Singleton graph. (diameter 2, girth 5, degree 7, order 50)
A hypothetical graph of diameter 2, girth 5, degree 57 and order 3250; it is currently unknown whether such a graph exists.
Unlike all other Moore graphs, Higman proved that the unknown Moore graph cannot be vertex-transitive.

This code should be pretty easy to compile as there are no requirements on any libraries outside of the standard right now.
I was going to accelerate this with cuda and omp, but a factor of 100 increase in speed wouldn't really help you with the 57
degree graph and would be unoticable with the 7 or 3 as they are already extremely fast. 
You will probably have to change the CC variable in the makefile to fit your system and you will need a c++ compiler that is 
modern enough to support C++11 features. 

About

No description, website, or topics provided.

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published