Purchase Solution

Strongly regular graph proof

Not what you're looking for?

Ask Custom Question

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.

Purchase this Solution
Solution Summary

This is a proof regarding a strongly regular graph.

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), ...

Purchase this Solution
Free BrainMass Quizzes
Geometry - Real Life Application Problems

Understanding of how geometry applies to in real-world contexts

Know Your Linear Equations

Each question is a choice-summary multiple choice question that will present you with a linear equation and then make 4 statements about that equation. You must determine which of the 4 statements are true (if any) in regards to the equation.

Graphs and Functions

This quiz helps you easily identify a function and test your understanding of ranges, domains , function inverses and transformations.

Multiplying Complex Numbers

This is a short quiz to check your understanding of multiplication of complex numbers in rectangular form.

Solving quadratic inequalities

This quiz test you on how well you are familiar with solving quadratic inequalities.

View More Free Quizzes
Related BrainMass Solutions

  • Adjacency matrix, Order and Valency

    Similarly JA=4J Now for the proof: Let us consider The last step uses the fact that the graph is regular such that the valency of every node is k.

  • Find values of p for which the faces of a planar p-regular graph are all triangles.

    Determine, with proof, the values of p for which this is possible. (Remember a p-regular graph has all vertices of degree p). Please see the attached file for the complete solution. Thanks for using BrainMass.

  • Floor function proof

    Without loss of generality, we can assume that the graph is connected. Now, K_2 is the only 1-regular graph (graph of regularity 1). Hence we have G r-regular with r >= 2. Consider any graph such that Kappa(G) = 1.

  • Proofs: K-Regular Graphs

    Proof 1) By contradiction. If G is a k-regular graph with order n, then the sum of degree over all vertices is k.n which is odd.

  • Prove that every regular tournament is strong.

    (3) A graph is strong, it means that for any vertices u and v in this graph, we can find a path from u to v. Now we want to show that D is strong. Proof: We consider two vertices u and v in D and assume D has 2k+1 vertices.

  • Bipartite Graphs

    Can you draw a graph for me please? Please see the attached file for the complete solution. Thanks for using BrainMass. a) Show that every bipartite graph G is a subgraph of a -regular bipartite graph. Proof.

  • A Nontrivial Connected Digraph

    The graph of a cycle is called a polygon - an equivalent definition being: a polygon is a finite connected graph that is regular and of degree 2.

  • Matching problem

    Proof: Let V1 be the set of people, and let V2 be the set of books. We can form a bipartite graph G=(V1, V2, E) as follows.

  • Graphing with Vertices

    Suppose G is a graph and (G)  n/3. Prove that G has one or two connected components. 7. a. Prove if n is odd, then there is no 3-regular graph with n vertices. b. Give an example of a 3-regular graph with 8 vertices. c.

View More Related Solutions