8
$\begingroup$

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?

EDIT:

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}$?

$\endgroup$
2
  • $\begingroup$ $G$ should not be complete graph, yes? $\endgroup$ Aug 20, 2014 at 11:01
  • $\begingroup$ @FedorPetrov Yes, let's exclude it. $\endgroup$ Aug 20, 2014 at 11:07

1 Answer 1

5
$\begingroup$

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

QED

$\endgroup$
1
  • 2
    $\begingroup$ Or without cases $k\geq 2\lambda+3-\nu>2\lambda-2\nu$. $\endgroup$ Aug 21, 2014 at 14:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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