TOPICS
Search

Two-Regular Graph


A two-regular graph is a regular graph for which all local degrees are 2. A two-regular graph consists of one or more (disconnected) cycles.

Two-RegularGraphs

The numbers a_n of two-regular graphs on n=1, 2, ... nodes are 0, 0, 1, 1, 1, 2, 2, 3, 4, 5, ... (OEIS A008483), which are equivalent to the numbers of partitions of n into parts >=3. The first few such graphs are illustrated above.

This sequence has closed form

 a_n=P(n-3)-P(n-2)-P(n-1)+P(n),
(1)

where P(n) is the partition function P. It also has generating function given by

G(x)=sum_(n=1)^(infty)a_nx^n
(2)
=-1+sum_(k=3)^(infty)1/(1-x^k)
(3)
=((x-1)^2(x+1))/((x)_infty)-1,
(4)

where (x)_infty is a q-Pochhammer symbol.


See also

Cycle Graph, Empty Graph, Regular Graph

Explore with Wolfram|Alpha

References

Sloane, N. J. A. Sequence A008483 in "The On-Line Encyclopedia of Integer Sequences."

Cite this as:

Weisstein, Eric W. "Two-Regular Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Two-RegularGraph.html

Subject classifications