Cycle Graph

In graph theory, a cycle graph , sometimes simply known as an -cycle (Pemmaraju and Skiena 2003, p. 248), is a graph on 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 (the triangle graph), (the square graph, also isomorphic to the grid graph ), (isomorphic to the bipartite Kneser graph ), and (isomorphic to the 2-Hadamard graph). The -cycle graph is isomorphic to the Haar graph as well as to the Knödel graph .

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

The chromatic number of is given by

(1)

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

			(2)
			(3)
			(4)
			(5)

where is a Chebyshev polynomial of the first kind. These correspond to recurrence equations

			(6)
			(7)
			(8)
			(9)

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

The bipartite double graph of is for odd, and for even.