Explore BrainMass

Strongly regular graph proof

Let n >= 2 be a number. Define the graph L2(n) as follows: Vertices are ordered pairs from the set {1, ..., n}. Two vertices are adjacent if they have the same first coordinate, or the same second coordinate (but not both).

Show that this is a strongly regular graph, and find its parameters.

Solution Preview

First, each node of this graph L2(n) is an ordered pair (a,b), where a,b
are selected from the set X={1,2,...,n}. Each a or b has n choices. Thus
the graph has v=n^2 nodes.
Second, I claim that this is a k-regular graph, where k=2(n-1).
For each node (a,b), it has neighbors (a,r), ...

Solution Summary

This is a proof regarding a strongly regular graph.