3
$\begingroup$

Show that a strongly regular graph with $28$ verticies each with valency $9$ such that adjacent pairs are not joined and non-adjacent pairs share exactly $4$ vertices does not exist.

A really bad proof is the following: If such an object existed, some clever spark would have found it, and despite an extensive search I have not found it in the literature. I have a toe curling argument involving 4 subsets of a 9 set and then some, that doesn't even convince me!

Is there a reasonably simple counting arguement that shows the non-existence of this? Failing that a reference to a computer search that shows it?

As usual my thanks in advance to all who offer a response. HK

  • 1
    Nice one Jerry! This explains why no one responded to this queston. I meant to say that if two verticies are adjacent then there are no other verticies that are mutually adjacent to these two veticies. (This is the zero as the third parameter in the question, google strongly regular graphs!) This problem is still my drop off to sleep thoughts.2012-06-06

1 Answers 1

3

A useful resource for strongly regular graphs and graph spectra in general is prof. dr. Andries E. Brouwer's website (see e.g. his tables of parameters and existence/uniqueness) and his lecture notes on spectra of graphs. On page 117-118 of the preprint you will find conditions on the parameters that have to be satisfied by any set of parameters, which are not satisfied by the parameter set $(28,9,0,4)$. This example is actually explicitly mentioned there, not satisfying the bound $v \leq g (g+3) / 2$ (in this case $v = 28$ and $g = 6$).