Strongly regular graph
Encyclopedia : S : ST : STR : Strongly regular graph
Definition
Let G=(V,E) be a regular graph with v vertices and degree k. It is by definition strongly regular if there are also integers [\lambda] and [\mu] such that :
- Every two adjacent vertices have [\lambda] common neighbours.
- Every two non-adjacent vertices have [\mu] common neighbours.
Some authors exclude a family of graphs which satisfy the definition trivially, namely those graphs which are the disjoint union of one or more equal-sized complete graphs, and the complements of those (which include the empty graphs and the complete bipartite graphs).
Properties
- The four parameters in [srg(v,k,\lambda,\mu)] are not independent, as it can easily be obtained that [(v-k-1)\mu=k(k-\lambda-1)].
- Let J denote the matrix such that [J_=1]. The adjacency matrix A of such a graph satisfies these properties :
- * [A J = k J]
- * [A^2+(\mu-\lambda) A+(\mu-k) I=\mu J]
- The eigenvalues are all integers, except when the strongly regular graph is a conference graph.
- The complement of an [srg(v,k,\lambda,\mu)] is also strongly regular. It is a [srg(v,v-k-1,v-2k+\mu-2,v-2k+\lambda)].
From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.