- Strongly regular graph
Let "G = (V,E)" be a
regular graphwith "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 graphwith diameter 2, but only if μ is non-zero.
* 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 :where The multiplicities of the eigenvalues are:where
* 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 graphbecause 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"+λ).
* The cycle of length 5.
Seidel adjacency matrix
* [http://mathworld.wolfram.com/StronglyRegularGraph.html Mathworld article with numerous examples.]
* 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