Regular graph: Difference between revisions
→Algebraic properties: {{fact|date=February 2009}} |
mNo edit summary |
||
| Line 20: | Line 20: | ||
==Algebraic properties== |
==Algebraic properties== |
||
Let ''A'' be the [[adjacency matrix]] of the graph. Now the graph is regular [[if and only if]] <math>\begin{bmatrix}1\\ \vdots \\1 \end{bmatrix}</math> is an [[eigenvector]] of ''A''. |
Let ''A'' be the [[adjacency matrix]] of the graph. Now the graph is regular [[if and only if]] <math>\begin{bmatrix}1\\ \vdots \\1 \end{bmatrix}</math> is an [[eigenvector]] of ''A''.<ref>Cvetković, D. M.; Doob, M.; and Sachs, H. Spectra of Graphs: Theory and Applications, 3rd rev. enl. ed. New York: Wiley, 1998.</ref> When it is an eigenvector, the eigenvalue will be the constant degree of the graph. |
||
When the graph is regular with degree ''k'', the graph will be connected if and only if ''k'' has algebraic (and geometric) dimension one.{{fact|date=February 2009}} |
When the graph is regular with degree ''k'', the graph will be connected if and only if ''k'' has algebraic (and geometric) dimension one.{{fact|date=February 2009}} |
||
Revision as of 22:25, 19 February 2009
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 k‑regular graph or regular graph of degree k.
Regular graphs of degree at most 2 are easy to classify: A 0-regular graph consists of disconnected vertices, a 1-regular graph consists of disconnected edges, and a 2-regular graph consists of disconnected cycles.
A 3-regular graph is known as a cubic graph.
A strongly regular graph is a regular graph where every adjacent pair of vertices has the same number l of neighbors in common, and every non-adjacent pair of vertices has the same number n of neighbors in common. The smallest graphs that are regular but not strongly regular are the cycle graph and the circulant graph on 6 vertices.
The complete graph is strongly regular for any .
A theorem by Nash-Williams says that every k‑regular graph on 2k + 1 vertices has a Hamiltonian cycle.
0-regular graph
1-regular graph
2-regular graph
3-regular graph
Algebraic properties
Let A be the adjacency matrix of the graph. Now the graph is regular if and only if is an eigenvector of A.[1] When it is an eigenvector, the eigenvalue will be the constant degree of the graph.
When the graph is regular with degree k, the graph will be connected if and only if k has algebraic (and geometric) dimension one.[citation needed]
There is also a criterion for regular and connected graphs : a graph is connected and regular if and only if the matrix J, with , is in the adjacency algebra of the graph (meaning it is a linear combination of powers of A).[citation needed]
Generation
Regular graphs may be generated by GenReg program. [2]
See also
References
External links
- Weisstein, Eric W. "Regular Graph". MathWorld.
- Weisstein, Eric W. "Strongly Regular Graph". MathWorld.
- Nash-Williams, Crispin (1969), "Valency Sequences which force graphs to have Hamiltonian Circuits", University of Waterloo Research Report, Waterloo, Ontario: University of Waterloo