Talk:Strongly regular graph

Potentially inaccurate statement in examples

I am not an expert on graph theory, so I hesitate to update the article itself. However, I believe the categorical statement:

The strongly regular graphs with λ=0 are triangle free. The seven listed above are the only known ones.

is incorrect. If I understand the subject correctly, every complete bipartite graph on an even number of vertexes is also strongly regular, with signature srg(2 k, k, 0, k), and bipartite graphs with signature srg(2 k, k, 0, p), with p < k, are easily constructed. — Preceding unsigned comment added by 98.26.29.11 (talk) 12:45, 22 May 2012 (UTC)

I need to retract the construction remark - the only strongly regular bipartite graphs are complete.

Proof of $(v-k-1)\mu =k(k-\lambda -1)$

I was unable to find a reference to cite for this formula. However, the proof is pretty simple:

Consider a strongly regular graph G with parameters (v,k,λ,μ) and vertex set V. Let n(x) be the set of vertexes in V that are adjacent to the vertex x in G, and let p(x) be the set of vertexes in V that are neither the vertex x nor in n(x). Then, consider a particular vertex q. Every vertex t in n(q) forms an edge with λ vertexes in n(q). Further, t forms an edge with q. This leaves k-λ-1 edges that have one vertex in n(q) and one vertex in p(q). Taken over all vertexes adjacent to q, this gives k (k-λ-1).

Next, consider the set of vertexes p(q). For every vertex t in p(q), q forms an edge with μ vertexes in n(t). By the partitioning of V, there are v-k-1 vertexes in p(q). Thus, the vertexes in p(q) form (v-k-1) μ edges with the vertexes in n(q). But this is the same set of edges that were counted in the preceding paragraph. Hence, (v-k-1) μ = k (k-λ-1). — Preceding unsigned comment added by 66.194.221.34 (talk) 16:48, 4 June 2012 (UTC)

Etymology paragraph and definitions

The etymology paragraph in its current state is confusing. The definition at the beginning of the article does not exclude the complete or the edgeless graph. Then the first paragraph of the etymology section suggests that complete multipartite graphs are usually excluded. Then the second paragraph of the etymology sections cites the definition in Brouwer-Van Maldeghem (BVM), but it does not cite it correctly. In BVM complete multipartite graphs are also strongly regular graphs. Disjoint unions of complete graphs and complete multipartite graphs are called imprimitive, while all other strongly regular graphs are primitive. Of course only primitive strongly regular graphs are interesting, but this is not the point here.

Probably, the article should settle on one definition of a strongly regular graph and mention the others. There are three options. (1) Do not exclude any. (2) Only exclude the complete and the edgeless graph. (3) Exclude all SRGs which BVM calls imprimitive SRGs.

For (1) one the spectral arguments are slightly off, so (2) or (3) are better choices. Maybe (2) is the best option as it coincides with Brouwer's book and it probably the most standard notation. FIhringer (talk) 12:40, 6 May 2023 (UTC)