suppose $G$ is strongly regular graph srg$(n,k,\lambda,\mu)$,prove that $k\geq 2\lambda -\mu +3 $.

310 Views Asked by At

suppose $G$ is strongly regular graph srg$(n,k,\lambda,\mu)$,prove that $k\geq 2\lambda -\mu +3 $.

I tried to show that $\mu(n-1)\geq k(\lambda+2)$(*) if I can prove that,then I add $-\mu k$ to both side of inequality then we have $$\mu n-\mu k -\mu \geq k\lambda -k\mu +2k $$

$$\mu(n-k-1)\geq k(\lambda - \mu +2 )$$

using $ \mu(n-k-1)=k(k-\lambda -1)$ we have

$$k(k-\lambda -1) \geq k(\lambda - \mu +2 )$$

and then $$(k-\lambda -1) \geq (\lambda - \mu +2 ) \rightarrow k \geq 2\lambda -\mu +3$$

but I couldn't prove the (*) .

it will be great if you help me with this ,thanks.

1

There are 1 best solutions below

0
On BEST ANSWER

We can suppose that $\mu\geq 1$, therefore there exist three vertices $u_1,u_2,u_3$ such that $u_2u_3$ is a non-edge, but $u_1u_2$ and $u_1u_3$ are edges. Denote $a$ the number of vertices which are common neighbours of the chosen vertices $u_1,u_2,u_3$. Clearly, $a\leq \mu-1$. (Minus one, because $u_1$ is a common neighbour of $u_2$ and $u_3$.)

For example, after drawing a picture, it is easy to see that the set $B$ containing vertices, which are joined to $u_1$, but are not neighbours of $u_2$ nor $u_3$ has cardinality equal to $k-(a+2(\lambda-a)+2)$.

Obviously, $|B|\geq 0$. Thus, $$k\geq a + 2(\lambda - a) + 2$$ and using $a \leq \mu-1$ we, finally, obtain $$k \geq 2\lambda +3-\mu.$$