Regular graph

Материал из WikiGrapp
Перейти к:навигация, поиск

Regular graph --- регулярный граф, однородный граф.

G is a regular graph of degree k, if every vertex is incident with k edges (i.e., every vertex has the degree equal to k).

A graph that is not regular is mathcalled irregular. It is well known that a simple graph must have at least two vertices of the same degree. If a graph has exactly two vertices of the same degree, we mathcall it a maximally irregular graph.

If multiple edges and loops are allowed, the degree sequences in which all elements are distinct are realizable. If no two vertices of a graph have the same degree, we mathcall it a totally irregular graph. It is obvious that a totaly irregular graph cannot be a simple graph.

A graph is (r,s)-regular, if the degree of each vertex is either r or s.