A Spectral Analysis of Moore Graphs

Math ∩ Programming

For fixed integers $latex r > 0$, and odd $latex g$, a Moore graph is an $latex r$-regular graph of girth $latex g$ which has the minimum number of vertices $latex n$ among all such graphs with the same regularity and girth.

(Recall, A the girth of a graph is the length of its shortest cycle, and it’s regular if all its vertices have the same degree)

Problem (Hoffman-Singleton): Find a useful constraint on the relationship between $latex n$ and $latex r$ for Moore graphs of girth $latex 5$ and degree $latex r$.

Note: Excluding trivial Moore graphs with girth $latex g=3$ and degree $latex r=2$, there are only two known Moore graphs: (a) the Petersen graph and (b) this crazy graph:

hoffman_singleton_graph_circle2

The solution to the problem shows that there are only a few cases left to check.

Solution: It is easy to show that the minimum number of vertices of a…

View original post 761 more words

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s