Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
"adjacent pairs are not joined"? What does that mean? If two vertices are adjacent, that means they are joined, no? –  Gerry Myerson Jun 6 '12 at 9:10
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. –  Herman Jun 6 '12 at 16:14
    
Dear TMM this is not homework. I would use the tag if it was. Thanks for your answer. This is very helpful. I have an excel spread sheet that generates possible parameters for SRGs ... it does do some checks but I dont always look carefully enough. Thanks again. Herman K :+) –  Herman Jun 7 '12 at 16:03

1 Answer 1

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$).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.