Triangle free strongly regular graphs

Importance: High ✭✭✭
Recomm. for undergrads: no
Posted by: mdevos
on: May 28th, 2007

\begin{problem} Is there an eighth triangle free strongly regular graph? \end{problem}

A regular graph $G$ is \Def[strongly regular]{strongly regular graph} 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 \Def{Petersen Graph}, The Clebsch Graph, the \Def{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 \Def[Moore Graph]{Moore graph} of diameter 2 is a triangle-free strongly regular graph, so if there is a \OPref[57-regular Moore Graph]{57_regular_moore_graph} of diameter 2, this would add another to the list.

See \href[Andries Brouwer's graph descriptions]{} for more on these graphs.


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

* indicates original appearance(s) of problem.


I hate math..Lol _________________________________________________________________________________________ toll free number

The complement of $2 K_n$

The complement of $2 K_n$ is triangle free srg with parameters $(2n,n,0,n)$. Probably this infinite case should be excluded from the conjecture.

If the number of the

If the number of the vertices are even, we can determine regular triangle free graphs up to half the number of vertices of any degree. However, this does not hold true if the vertices numbers are odd. Some of the examples of even vertices graphs are Petersen graph (10 vertices), Heawood graph (14 vertices), Clebsch graph (16 vertices), Pappus graph (18 vertices) and odd vertices graph includes Schläfli graph (27 vertices), Perkel graph (57 vertices). 800 numbers

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.