## Strongly regular graphs

graph is called regular if its every vertex has the same number of neighbours. For example, this is a regular graph where each vertex has exactly three neighbours:

It is the well known Petersen graph which is so important and popular in graph theory that it even has a full book devoted to it. It is probably not the first example that will come to your mind when one talks about regular graphs. Some more basic examples would be, a cycle or the trivial graph where every vertex has precisely zero neighbours. But we are going to talk about graphs that are “strongly” regular and then the Petersen graph is probably the perfect graph to start the with (even though it isn’t really perfect).

Let’s collect some obvious facts that you can observe by looking at the picture. This graph has $10$ vertices, $15$ edges, degree $3$ and maximum distance of $2$ between any pair of points. If you observe it even more carefully then you would see that there are no triangles or squares in this graph, but clearly there is a pentagon (how many of those are there?). This is the same as saying that the girth of the Petersen graph is $5$Of course not all these parameters are independent. It can be easily proved that any regular graph of degree $3$ and diameter (maximum distance between two points) $2$ has at most $10$ vertices. And when that bound is achieved then the graph must necessarily have girth $5$. Therefore, Petersen graph is a maximal graph with fixed degree $3$ and fixed diameter $2$. In fact, it can be proved that Petersen graph is the maximal graph satisfying those conditions.

The fact that the Petersen graph has diameter $2$ and girth $5$ can also be written as, every pair of adjacent vertices have zero common neighbours and every pair of non-adjacent vertices have a unique common neighbour. This gives us the constants $(10, 3, 0, 1)$ where $10$ is the number of vertices, $3$ is the degree of each vertex, $0$ is the number of common neighbours between any pair of adjacent vertices and $1$ is the number of common neighbours between any pair of non-adjacent vertices. We have arrived at the definition of “strongly” regular graphs:

A graph $G$ is called a strongly regular graph (srg) with parameters $(v, k, \lambda, \mu)$ if it is $k$-regular with $v$ vertices and satisfies the following:

• every pair of adjacent vertices have exactly $\lambda$ common neighbours;
• every pair of non-adjacent vertices have exactly $\mu$ common neighbours.

Therefore, the Petersen graph is an $srg(10, 3, 0, 1)$. In fact, it is the only possible graph with those parameters. To make the idea more clear I would state that  a cycle of length $5$ is an $srg(5, 2, 0, 1)$ and that every complete graph on $n$ vertices is an $srg(n, n-1, n-2, 0)$. We would say that an $srg$ is non-trivial if the parameter $\mu$ is non zero, which makes the complete graph a trivial $srg$. For non-trivial srg’s we can easily show that the diameter must be $2$.

Now a crucial question, why are these graphs important? Or more specifically, why do mathematicians care about these graphs? I’ll try to give some reasons why. To quote Peter Cameron [1],

Strongly regular graphs stand on the cusp between the random and the highly structured.

One of the examples he gives is that while there is (up to isomorphism) a unique $srg(36, 10, 4, 2)$, the number of $srg(36, 15, 6, 6)$ is $32548$. Moreover, while many of the strongly regular graphs are highly symmetrical (the Petersen graph has an automorphism group of size $120$) there are strong indications that almost all strongly regular graphs are asymmetrical (trivial automorphism groups) [2,3].

Regarding the highly symmetrical srg’s, many of them are related to important finite groups which makes them interesting objects for group theorists. For example, this strongly regular graph of $100$ vertices has the sporadic simple Hall-Janko group of order $604800$ as its automorphism group:

(image by  Claudio Rochhini)

It belongs to a chain of strongly regular graphs called the Suzuki tower which correspond nicely to certain finite simple groups. In fact the Suzuki group was originally constructed as an automorphism group of the top most graph in that tower. Moreover, the $G_2(4)$ graph in that tower was used by Andriy V. Bondarenko last year to find the smallest counter example to the Borsuk’s conjecture in geometry [4]. Borsuk asked this question in 1933,

Can every bounded subset E of the space $\mathbb{R}^n$ be partitioned into $(n+1)$ sets, each of which has a smaller diameter than E?

It was proved that the answer is yes for several small cases and also in general if you assume some extra conditions. But in 1993 it was shown by Kalai and Kahn that the general answer to this problem is no. They found a counter example in dimension $1325$ and for every dimension greater than $2014$. The example that Bondarenko constructed was in dimension $65$.

There are strongly regular graphs corresponding to latin squaresgeneralized quadranglesassociation schemesHadamard matrices, designs, sporadic groups, root systems and several other combinatorial/algebraic structures in mathematics. They pop up in the strangest of places from quantum physics [5], to computational complexity theory [6], to theoretical chemistry [7]. And I believe that they are highly interesting mathematical objects in their own right.

For more on these graphs, you can refer to [1] or this book by Brouwer and Haemers. These graphs were originally introduced by R.C. Bose in this paper from 1963. An interesting blog post on triangle free strongly regular graphs by Peter Cameron can be found here.

[1] Strongly Regular Graphs by Cameron (and some more notes from his course at St Andrews on Advanced Combinatorics)
[2] Are almost all srg’s rigid? (mathoverflow)
[3] Examples of rigid srg’s (mathoverflow)
[4] On Borsuk’s conjecture for two-distance sets
[
5] Global Symmetry is Unnecessary for Fast Quantum Search
[
6] On the Automorphism Groups of Strongly Regular Graphs
[7] Energy of graphs
[8] Strongly Regular Graphs by Brouwer

A mathematician working at FU Berlin as a postdoc. I am broadly interested in combinatorics and finite geometry.
This entry was posted in Combinatorics and tagged . Bookmark the permalink.

### 3 Responses to Strongly regular graphs

1. Pingback: Count Twice! | Anurag's Math Blog

2. Some basic properties of strongly regular graphs that one can take as exercises:

1. Let $\Gamma$ be a strongly regular graph with parameters $(v, k, \lambda, \mu)$, then its complement $\overline{\Gamma}$ is a strongly regular graph with parameters $(v, v - k - 1, v - 2k + \mu - 2, v - 2k + \lambda)$.

2. Let $\Gamma$ be a strongly regular graph with parameters $(v, k, \lambda, \mu)$, then $\mu \leq k$, with equality if and only if $\Gamma$ is a complete multipartite graph.

3. Let $\Gamma$ be a strongly regular graph with parameters $(v, k, \lambda, \mu)$, then $\lambda + 1 \leq k$, and the following are equivalent: (i) $\Gamma$ is a disjoint union of complete graphs; (ii) $k = \lambda + 1$; (iii) $\mu = 0$; (iv) $\Gamma$ is disconnected.