The Full Wiki



More info on Strongly regular graph

Strongly regular graph: Wikis

Note: Many of our articles have direct quotes from sources you can cite, within the Wikipedia article! This article doesn't yet, but we're working on it! See more info or our list of citable articles.

Encyclopedia

Updated live from Wikipedia, last check: May 15, 2013 11:25 UTC (46 seconds ago)

From Wikipedia, the free encyclopedia

The Paley graph of order 13, a strongly regular graph with parameters srg(13,6,2,3).
Graph families defined by their automorphisms
distance-transitive \rightarrow distance-regular \leftarrow strongly regular
\downarrow
symmetric (arc-transitive) \leftarrow t-transitive, t ≥ 2
\downarrow(if connected)
vertex- and edge-transitive \rightarrow edge-transitive and regular \rightarrow edge-transitive
\downarrow \downarrow
vertex-transitive \rightarrow regular
\uparrow
Cayley graph skew-symmetric

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 non-adjacent vertices have μ common neighbours.

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

Some authors exclude[citation needed] 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.

Contents

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 (of order v) and let J denote the matrix whose entries all equal 1. The adjacency matrix A of a strongly regular graph satisfies these properties :
    • A\times J = kJ
      (This is a trivial restatement of the vertex degree requirement).
    • A2 + (μ − λ)A + (μ − k)I = μJ
      (The first term gives the number of 2-step paths from each vertex to all vertices. For the vertex pairs directly connected by an edge, the equation reduces to the number of such 2-step paths being equal to λ. For the vertex pairs not directly connected by an edge, the equation reduces to the number of such 2-step paths being equal to μ. For the trivial self-pairs, the equation reduces to the degree being equal to k).
  • The graph has exactly three eigenvalues:
    • k whose multiplicity is 1
    • \frac{1}{2}\left[(\lambda-\mu)+\sqrt{(\lambda-\mu)^2 + 4(k-\mu)}\right] whose multiplicity is \frac{1}{2} \left[(v-1)-\frac{2k+(v-1)(\lambda-\mu)}{\sqrt{(\lambda-\mu)^2 + 4(k-\mu)}}\right]
    • \frac{1}{2}\left[(\lambda-\mu)-\sqrt{(\lambda-\mu)^2 + 4(k-\mu)}\right] whose multiplicity is \frac{1}{2} \left[(v-1)+\frac{2k+(v-1)(\lambda-\mu)}{\sqrt{(\lambda-\mu)^2 + 4(k-\mu)}}\right]
  • Strongly regular graphs for which 2k + (v − 1)(λ − μ) = 0 are called conference graphs because of their connection with symmetric conference matrices. Their parameters reduce to srg\left(v, \frac{v-1}{2}, \frac{v-5}{4}, \frac{v-1}{4}\right).
  • Strongly regular graphs for which 2k+(v-1)(\lambda-\mu) \ne 0 have integer eigenvalues with unequal multiplicities.
  • The complement of an srg(v,k,λ,μ) is also strongly regular. It is an srg(v, v−k−1, v−2−2k+μ, v−2k+λ).

Examples

See also

Notes

  1. ^ Weisstein, Eric W., "Schläfli graph" from MathWorld.

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

External links








Got something to say? Make a comment.
Your name
Your email address
Message