Strongly regular graph - Alchetron, The Free Social Encyclopedia

→ {displaystyle {oldsymbol {ightarrow }}} distance-regular ← {displaystyle {oldsymbol {leftarrow }}} t-transitive, t ≥ 2 → {displaystyle {oldsymbol {ightarrow }}} regular		← {displaystyle {oldsymbol {leftarrow }}} strongly regular → {displaystyle {oldsymbol {ightarrow }}} edge-transitive

→ {displaystyle {oldsymbol {ightarrow }}} edge-transitive and regular

In graph theory, a strongly regular graph is defined as follows. Let G = (V,E) be a regular graph with v vertices and degree k. G is said to be strongly regular if there are also integers λ and μ such that:

Relationship between Parameters

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

( v − k − 1 ) μ = k ( k − λ − 1 )

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 k − λ − 1 edges remaining for each Level 1 node to connect to nodes in Level 2. Therefore, there are k × ( k − λ − 1 ) edges between Level 1 and 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. There are ( v − k − 1 ) nodes in Level 2, and each is connected to μ nodes in Level 1. Therefore the number of edges between Level 1 and Level 2 is ( v − k − 1 ) × μ .

Equating the two expressions for the edges between Level 1 and Level 2, the relation follows.

Adjacency Matrix

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 two equations. First,

A J = J A = k J ,

which is a trivial restatement of the vertex degree requirement; incidentally, this shows that k is an eigenvalue of the adjacency matrix with an all-ones eigenvector. Second,

A 2 + ( μ − λ ) A + ( μ − k ) I = μ J ,

which expresses the strong regularity condition. The first term gives the number of 2-step paths from each vertex to all vertices, the second term the 1-step paths, and the third term the 0-step paths (so to speak). 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.

Conversely, a graph which is not a complete or null graph whose adjacency matrix satisfies both of the above conditions is a strongly regular graph.

Eigenvalues

The adjacency matrix of the graph has exactly three eigenvalues:

k whose multiplicity is 1 (as seen above)

1 2 [ ( λ − μ ) + ( λ − μ ) 2 + 4 ( k − μ ) ] whose multiplicity is 1 2 [ ( v − 1 ) − 2 k + ( v − 1 ) ( λ − μ ) ( λ − μ ) 2 + 4 ( k − μ ) ]

1 2 [ ( λ − μ ) − ( λ − μ ) 2 + 4 ( k − μ ) ] whose multiplicity is 1 2 [ ( v − 1 ) + 2 k + ( v − 1 ) ( λ − μ ) ( λ − μ ) 2 + 4 ( k − μ ) ]

As the multiplicities must be integers, their expressions provide further constraints on the values of v, k, μ, and λ, related to the so-called Krein conditions.

Strongly regular graphs for which 2 k + ( v − 1 ) ( λ − μ ) = 0 are called conference graphs because of their connection with symmetric conference matrices. Their parameters reduce to

Strongly regular graphs for which 2 k + ( v − 1 ) ( λ − μ ) ≠ 0 have integer eigenvalues with unequal multiplicities.

Examples

The cycle of length 5 is an srg(5, 2, 0, 1).

The Petersen graph is an srg(10, 3, 0, 1).

The Clebsch graph is an srg(16, 5, 0, 2).

The Shrikhande graph is an srg(16, 6, 2, 2) which is not a distance-transitive graph.

The Line graph of generalized quadrangle GQ(2, 4) is an srg(27, 10, 1, 5). In fact every generalized quadrangle of order (s, t) gives a strongly regular graph in this way.

The Schläfli graph is an srg(27, 16, 10, 8).

The Chang graphs are srg(28, 12, 6, 4).

The Hoffman–Singleton graph is an srg(50, 7, 0, 1).

The Sims-Gewirtz graph is an (56, 10, 0, 2).

The M₂₂ graph is an srg(77, 16, 0, 4).

The Brouwer–Haemers graph is an srg(81, 20, 1, 6).

The Higman–Sims graph is an srg(100, 22, 0, 6).

The Local McLaughlin graph is an srg(162, 56, 10, 24).

The Cameron graph is an srg(231, 30, 9, 3).

The Paley graph of order q is an srg(q, (q − 1)/2, (q − 5)/4, (q − 1)/4).

The n × n square rook's graph is an srg(n², 2n − 2, n − 2, 2).

A strongly regular graph is called primitive if both the graph and its complement are connected. All the above graphs are primitive, as otherwise μ=0 or μ=k.

Moore graphs

The strongly regular graphs with λ = 0 are triangle free. Apart from the complete graphs on less than 3 vertices and all complete bipartite graphs the seven listed above are the only known ones. Strongly regular graphs with λ = 0 and μ = 1 are Moore graphs with girth 5. Again the three graphs given above, with parameters (5, 2, 0, 1), (10, 3, 0, 1) and (50, 7, 0, 1), are the only known ones. The only other possible set of parameters yielding a Moore graph is (3250, 57, 0, 1); it is unknown if such a graph exists, and if so, whether or not it is unique.

References

Strongly regular graph Wikipedia

(Text) CC BY-SA