Strongly regular graph: Difference between revisions

From Graph
(Created page with "{{undirected graph}} ==Definition== ===Definition for finite graphs=== Suppose <matH>G</math> is a finite undirected graph with <math>n</math> vertices...")
(No difference)

Revision as of 02:31, 28 May 2012

Template:Undirected graph

Definition

Definition for finite graphs

Suppose is a finite undirected graph with vertices. Suppose are nonnegative integers. We say that is a strongly regular graph of type (we sometimes write this as ) if it satisfies all of the following conditions:

  1. is a -regular graph, i.e., the degree of every vertex of equals .
  2. Any two adjacent vertices of have precisely vertices that are adjacent to both of them.
  3. Any two non-adjacent vertices of have precisely vertices that are adjacent to both of them.

Relation with other properties

Stronger properties

Property Meaning Proof of implication Proof of strictness (reverse implication failure) Intermediate notions
complete graph
empty graph