Regular graph

related topics
{math, number, function}
{line, north, south}

In graph theory, a regular graph is a graph without loops and multiple edges where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other.[1] 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 Km is strongly regular for any m.

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

Contents

Algebraic properties

Let A be the adjacency matrix of a graph. Then the graph is regular if and only if \textbf{j}=(1, \dots ,1) is an eigenvector of A.[2] Its eigenvalue will be the constant degree of the graph. Eigenvectors corresponding to other eigenvalues are orthogonal to \textbf{j}, so for such eigenvectors v=(v_1,\dots,v_n), we have \sum_{i=1}^n v_i = 0.

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

Full article ▸

related documents
Linear function
Inner automorphism
Subring
Elias gamma coding
Earley parser
Connectedness
Parse tree
Hausdorff maximal principle
Subset
Row and column spaces
Identity matrix
Profinite group
Axiom of power set
Unitary matrix
Injective function
Additive function
Random sequence
Unit interval
Inequation
Kleene star
Sharp-P
Specification language
Inverse functions and differentiation
Euler's identity
Class (set theory)
Disjunctive normal form
Endomorphism
Inverse transform sampling
Just another Perl hacker
Sum rule in differentiation