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

  • 0
    "adjacent pairs are not joined"? What does that mean? If two vertices are adjacent, that means they are joined, no?2012-06-06
  • 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