TOPICS
Search

Cycle Graph


CycleGraphs

In graph theory, a cycle graph C_n, sometimes simply known as an n-cycle (Pemmaraju and Skiena 2003, p. 248), is a graph on n nodes containing a single cycle through all nodes. A different sort of cycle graph, here termed a group cycle graph, is a graph which shows cycles of a group as well as the connectivity between the group cycles.

Cycle graphs can be generated in the Wolfram Language using CycleGraph[n]. Precomputed properties are available using GraphData[{"Cycle", n}]. A graph may be tested to see if it is a cycle graph using PathGraphQ[g] && Not[AcyclicGraphQ[g]], where the second check is needed since the Wolfram Language believes cycle graphs are also path graphs (a convention which seems nonstandard at best).

Special cases include C_3 (the triangle graph), C_4 (the square graph, also isomorphic to the grid graph G_(2,2)), C_6 (isomorphic to the bipartite Kneser graph H(3,1)), and C_8 (isomorphic to the 2-Hadamard graph). The 2n-cycle graph is isomorphic to the Haar graph H(2^(n-1)+1) as well as to the Knödel graph W_(2,2n).

Cycle graphs (as well as disjoint unions of cycle graphs) are two-regular. Cycle graphs are also uniquely Hamiltonian.

The chromatic number of C_n is given by

 chi(C_n)={3   for n odd; 2   for n even.
(1)

The chromatic polynomial, independence polynomial, matching polynomial, and reliability polynomial are

pi(x)=(x-1)^n+(-1)^n(x-1)
(2)
I(x)=2(-x)^(n/2)T_n(1/(2sqrt(-x)))
(3)
mu(x)=2^(-n)[(x-sqrt(x^2-4))^n+(x+sqrt(x^2-4))^n]
(4)
C(p)=(1-p)^(n-1)[1+(n-1)p].
(5)

where T_n(x) is a Chebyshev polynomial of the first kind. These correspond to recurrence equations

pi_n(x)=(x-2)pi_(n-1)(x)+(x-1)pi_(n-2)(x)
(6)
I_n(x)=I_(n-1)(x)+xI_(n-2)(x)
(7)
mu_n(x)=xmu_(n-1)(x)-mu_(n-2)(x)
(8)
C_n(x)=-2(x-1)C_(n-1)(x)-(x-1)^2C_(n-2)(x).
(9)

The line graph of a cycle graph C_n is isomorphic to C_n itself.

The bipartite double graph of C_n is C_(2n) for n odd, and 2C_n for n even.

The simplex graph of C_n for n>=4 is the gear graph G_n.


See also

Bipartite Kneser Graph, Characteristic Factor, Crossed Prism Graph, Cycle Index, Cyclic Graph, Graph Cycle, Haar Graph, Hadamard Graph, Hamiltonian Cycle, Kayak Paddle Graph, Knödel graph, Lollipop Graph, Pan Graph, Path Graph, Square Graph, Tadpole Graph, Triangle Graph, Two-Regular Graph, Walk Explore this topic in the MathWorld classroom

Explore with Wolfram|Alpha

References

Gross, J. T. and Yellen, J. Graph Theory and Its Applications. Boca Raton, FL: CRC Press, p. 13, 1999.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, p. 13, 1994.Pemmaraju, S. and Skiena, S. "Cycles, Stars, and Wheels." §6.2.4 in Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematica. Cambridge, England: Cambridge University Press, pp. 248-249, 2003.Skiena, S. "Cycles, Stars, and Wheels." §4.2.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 144-147, 1990.

Referenced on Wolfram|Alpha

Cycle Graph

Cite this as:

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

Subject classifications