Graph theory: strong regular graph

Question

A simple graph $G$ which is neither empty nor complete is said to be strongly regular with parameters $(v,k,λ,μ)$ if:
$$v(G)=v$$

$G$ is $k$-regular;
any two adjacent vertices of $G$ have $λ$ common neighbours,
any two nonadjacent vertices of $G$ have $μ$ common neighbours.

Let $G$ be strongly regular graph with parameters $(v,k,λ,μ)$. Show that:
a)$k(k-λ-1)=(v-k-1)μ,$
b)$A^2=kI+λA+μ( J-I-A) $
which $A $ is the adjacency matrix of $G$, I is the $ntimes n$ identity matrix and $J$ is the $ntimes n$ matrix all of whose entries are $1$. Any help would be great thanks.

Pegah Pournajafi · Answer

For part a)
Fix a vertex $x$ of the graph $G$. $x$ has some neighbors in $G$ (let's call them $N$) and has some non-neighbors (let's call them $M$). By hypothesis we have $|N|=k$ and $|M|=v-k-1$. Let the number of edges between $M$ and $N$ be $E=E[N,M]$. We find $E$, in two ways:
i) There are $v-k-1$ vertices in $M$, and each of them has $mu$ common neighbors with v, i.e. $deg_N(m)=mu    forall m in M$. Hence $E=(v-k-i)mu$.
ii) There are $k$ vertices in $N$, and for every $n in N$, $deg_G(n)=k$. But $n$ has $lambda$ common neighbors with $x$, so $deg_N(n)=lambda$. Therefore $deg_M(n)=k-lambda-1$ (notice that the $-1$ is for $x$). So $E=k(k-lambda -1)$.
This double counting completes the proof.
For part b)
Lets call the right side of the equality $B$.
for every $i$ and $j$, we will show that the $(i,j)$ entry of $A^2$ is equal to the $(i,j)$ entry of $B$.
First, notice that if $ineq j$ the $(i,j)$ entry of $A^2$ is the number of paths of length 2 between two vertices $i$ and $j$. It is not hard to see that the $(i,j)$ entry of $B$ is $mu$ when $insim j$ and is $lambda$ when $isim j$.
If $i=j$, the $(i,j)$ entry of $A^2$ is degree of vertex $i$, which is $k$ in this graph. The $(i,j)$ entry of $B$ is also k.

Graph theory: strong regular graph

One Answer

Add your own answers!

Ask a Question