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

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

1 Answer 1

Reset to default
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

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Or without cases $k\geq 2\lambda+3-\nu>2\lambda-2\nu$. $\endgroup$
    – Fedor Petrov
    Commented Aug 21, 2014 at 14:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .