Strongly Regular Graph - Properties

Properties

• The four parameters in an srg(v,k,λ,μ) are not independent and must obey the following relation:

The above relation can be derived very easily through a counting argument as follows:

• • Imagine the nodes of the graph to lie in three levels. Pick any node as the root node, in Level 0. Then its k neighbor nodes lie in Level 1, and all other nodes lie in Level 2.
  • Nodes in Level 1 are directly connected to the root, hence they must have other neighbors in common with the root, and these common neighbors must also be in Level 1. Since each node has degree k, there are edges remaining for each Level 1 node to connect to nodes in Level 2.
  • Nodes in Level 2 are not directly connected to the root, hence they must have common neighbors with the root, and these common neighbors must all be in Level 1. Therefore nodes in Level 1 are connected to each node in Level 2 and each of the k nodes in Level 1 is connected to nodes in Level 2. Therefore the number of nodes in Level 2 is .
  • The total number of nodes across all three levels is therefore and by rearranging we get . QED

• Let I denote the identity matrix (of order v) and let J denote the matrix whose entries all equal 1. The adjacency matrix A of a strongly regular graph satisfies these properties :
  • 
    (This is a trivial restatement of the vertex degree requirement).
  • 
    (The first term gives the number of 2-step paths from each vertex to all vertices. For the vertex pairs directly connected by an edge, the equation reduces to the number of such 2-step paths being equal to . For the vertex pairs not directly connected by an edge, the equation reduces to the number of such 2-step paths being equal to . For the trivial self-pairs, the equation reduces to the degree being equal to k).

• The graph has exactly three eigenvalues:
  • whose multiplicity is 1
  • whose multiplicity is
  • whose multiplicity is

• Strongly regular graphs for which are called conference graphs because of their connection with symmetric conference matrices. Their parameters reduce to .

• Strongly regular graphs for which have integer eigenvalues with unequal multiplicities.

• The complement of an srg(v,k,λ,μ) is also strongly regular. It is an srg(v, v−k−1, v−2−2k+μ, v−2k+λ).