Strongly regular graph

﻿
Strongly regular graph

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:

* Every two adjacent vertices have λ common neighbours.

* Every two non-adjacent vertices have μ common neighbours.

A graph of this kind is sometimes said to be an srg("v,k",λ,μ).

Some authors exclude graphs which satisfy the definition trivially, namely those graphs which are the disjoint union of one or more equal-sized complete graphs, and their complements, the Turán graphs.

A strongly regular graph is a distance-regular graph with diameter 2, but only if μ is non-zero.

Properties

* The four parameters in an srg("v,k",λ,μ) are not independent, as it is easy to show that (v−k−1)μ = k(k−λ−1).

* Let "I" denote the identity matrix and let "J" denote the matrix whose entries all equal 1. The adjacency matrix "A" of a strongly regular graph satisfies these properties :
** "A J = k J"
** "A"2 + (μ−λ) "A" + (μ−"k") "I" = μ "J".

* The graph has exactly three eigenvalues, one of which is the degree "k". The other eigenvalues can be expressed in terms of the parameters; they are :$frac\left\{1\right\}\left\{2\right\} \left[\left(lambda-mu\right) pm sqrt u\right] ,$where $u = \left(lambda-mu\right)^2 + 4\left(k-mu\right).$ The multiplicities of the eigenvalues are:$frac\left\{1\right\}\left\{2\right\} left \left[ \left(v-1\right) mp frac\left\{N\right\}\left\{sqrt u\right\} ight\right] ,$where $N = 2k + \left(v-1\right)\left(lambda-mu\right).$

* There are two kinds of strongly regular graph. If "N" = 0, then we have an srg("v", ("v"−1)/2, ("v"−5)/4, ("v"−1)/4). This kind is called a conference graph because of its connection with symmetric conference matrices. If "N" is nonzero, then the eigenvalues are all integers and their multiplicities are not equal.

* The complement of an srg("v,k",λ,μ) is also strongly regular. It is an srg("v, v−k"−1, "v"−2−2"k"+μ, "v"−2"k"+λ).

Examples

* The cycle of length 5.
* Petersen graph
* Hoffman-Singleton graph
* Higman-Sims graph
* Paley graphs
* Square rook's graphs

ee also

* [http://mathworld.wolfram.com/StronglyRegularGraph.html Mathworld article with numerous examples.]

References

* A.E. Brouwer, A.M. Cohen, and A. Neumaier (1989), "Distance Regular Graphs". Berlin, New York: Springer-Verlag. ISBN 3-540-50619-5, ISBN 0-387-50619-5

* Chris Godsil and Gordon Royle (2004), "Algebraic Graph Theory". New York: Springer-Verlag. ISBN 0-387-95241-1

Wikimedia Foundation. 2010.

Look at other dictionaries:

• Regular graph — In graph theory, a regular graph is a graph where each vertex has the same number of neighbors, i.e. every vertex has the same degree or valency. A regular graph with vertices of degree k is called a kregular graph or regular graph of degree… …   Wikipedia

• Distance-regular graph — Graph families defined by their automorphisms distance transitive distance regular strongly regular …   Wikipedia

• Graph theory — In mathematics and computer science, graph theory is the study of graphs : mathematical structures used to model pairwise relations between objects from a certain collection. A graph in this context refers to a collection of vertices or nodes and …   Wikipedia

• Graph (mathematics) — This article is about sets of vertices connected by edges. For graphs of mathematical functions, see Graph of a function. For statistical graphs, see Chart. Further information: Graph theory A drawing of a labeled graph on 6 vertices and 7 edges …   Wikipedia

• Glossary of graph theory — Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with… …   Wikipedia

• Clebsch graph — Named after Alfred Clebsch Vertices 16 Edges 40 …   Wikipedia

• Claw-free graph — A claw In graph theory, an area of mathematics, a claw free graph is a graph that does not have a claw as an induced subgraph. A claw is another name for the complete bipartite graph K1,3 (that is, a star graph with three edges, three leaves, and …   Wikipedia

• Turán graph — The Turán graph T(13,4) Named after Pál Turán v · …   Wikipedia

• Rook's graph — infobox graph name = Rook s graph image caption = 8x8 Rook s graph vertices = nm edges = nm ( n + m )/2 nm diameter = 2 chromatic number = max( n , m ) chromatic index = girth = 3 (if max( n , m ) ≥ 3) properties = regular, vertex transitive,… …   Wikipedia

• Shrikhande graph — infobox graph name = Shrikhande graph image caption = The Shrikhande graph drawn symmetrically. namesake = S. S. Shrikhande vertices = 16 edges = 48 chromatic number = chromatic index = properties = Strongly regularThe Shrikhande graph is a named …   Wikipedia