Let $G \neq K_{v}$ be a $(v,k,\lambda,\mu)$ strongly regular graph. After perusing through Brouwer's tables of parameters I have formed the conjecture $$\lambda-\mu \leq \frac{k}{2}.$$

So far I have not been able to prove it, though it seems like an easy statement. Have you seen something like this?


Now that the original claim is proved, we can ask: what is the best possible constant $C$ so that $\lambda-\mu \leq \frac{k}{C}$?

  • $\begingroup$ $G$ should not be complete graph, yes? $\endgroup$ – Fedor Petrov Aug 20 '14 at 11:01
  • $\begingroup$ @FedorPetrov Yes, let's exclude it. $\endgroup$ – Felix Goldberg Aug 20 '14 at 11:07

I have found a proof now. There is an old result, due originally to Taylor & Levingston, which says that for a strongly regular $G \neq K_{v}$:

$$ k \geq 2\lambda+3-\mu. $$

It can be found on page 7 of the BCN book and in fact holds for a more general class (the so-called amply regular graphs) as pointed out by Neumaier.

Now we can prove the claim in the question by considering two cases:

(I) $\lambda \leq \frac{k}{2}$. Then $\lambda-\mu \leq \lambda \leq \frac{k}{2}$.

(II) $\lambda>\frac{k}{2}$. Then $\lambda-\mu \leq (k-\lambda)-3<k-\lambda<\frac{k}{2}$.


  • 2
    $\begingroup$ Or without cases $k\geq 2\lambda+3-\nu>2\lambda-2\nu$. $\endgroup$ – Fedor Petrov Aug 21 '14 at 14:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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