Regular graph

In graph theory, a graph is called regular if all of its nodes have the same number of neighbors, ie have the same degree. In a regular directed graph must continue to apply the stronger condition that all nodes have the same input and output degrees. A regular graph with nodes of degree k is called k-regular or regular graph of degree k.

Regular graphs with a degree of at most 2 can be easily classified: A 0 - regular graph consists of disconnected nodes, a 1- regular graph consists of disjoint edges, and a 2- regular graph consists of disjoint circles.

3- regular graph is also referred to as a cubic graph.

A strongly regular graph is a regular graph in which each two adjacent nodes exactly a common neighbors, and the two non-adjacent nodes have exactly b common neighbors. The smallest regular but not strongly regular graph is a circle graph and the circular graph with 6 nodes.

The complete graph is strongly regular for each.

By a theorem of Nash -Williams, every k- regular graph with nodes a Hamilton cycle.

1- regular graph

2- regular graph

3- regular graph

Algebraic properties

Let A be the adjacency matrix of a graph. The graph is regular if an eigenvector of A is. The eigenvalue of this vector is the same as the level of the graph. Eigenvectors with different eigenvalues ​​are orthogonal to, ie for such eigenvectors applies.

A regular graph of degree k if and only connected if the eigenvalue k has multiplicity one has.