Home » Subject » Graph Theory » Algebraic G.T.
Importance: High ✭✭✭
Author(s):
Subject: Graph Theory
» Algebraic Graph Theory
Keywords: strongly regular
triangle free
Recomm. for undergrads: no
Posted by: mdevos
on: May 28th, 2007
Problem   Is there an eighth triangle free strongly regular graph?

A regular graph $ G $ is strongly regular if there exist integers $ \lambda, \mu $ so that every pair of adjacent vertices have exactly $ \lambda $ common neighbors, and every pair of nonadjacent vertices have exactly $ \mu $ common neighbors. To eliminate degeneracies, we shall further assume that $ \mu \ge 1 $. If $ G $ is $ k $-regular and $ |V(G)| = n $, then we say that $ G $ is a $ (n,k,\lambda,\mu) $ strongly regular graph.

There are exactly seven triangle-free strongly regular graphs known: The five cycle, the Petersen Graph, The Clebsch Graph, the Hoffman-Singleton Graph, The Gewirtz Graph, the Higman-Sims Graph, and a $ (77,16,0,4) $ strongly regular subgraph of the Higman-Sims graph. Every Moore Graph of diameter 2 is a triangle-free strongly regular graph, so if there is a 57-regular Moore Graph of diameter 2, this would add another to the list.

See Andries Brouwer's graph descriptions for more on these graphs.

Bibliography

[G] C. D. Godsil, Problems in Algebraic Combinatorics, Electronic Journal of Combinatorics, Volume 2, F1


* indicates original appearance(s) of problem.
4 comments

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options