TransWikia.com

Graph theory: strong regular graph

Mathematics Asked by Spencer Ireland on February 7, 2021

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.

One 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.

Answered by Pegah Pournajafi on February 7, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP