Cycle Polynomial

One would think that by analogy with the matching-generating polynomial, independence polynomial, etc., a cycle polynomial whose coefficients are the numbers of cycles of length k would be defined. While no such polynomial seems not to have been defined in the literature (instead, "cycle polynomials" commonly instead refers to a polynomial corresponding to cycle indices of permutation groups), they are defined in this work.

The cycle polynomial, perhaps defined here for the first time, is therefore the polynomial


whose coefficients c_k give the number of simple cycles present in a graph G on n nodes.

Since the smallest possible cycle is of length 3, cycle polynomials have polynomial degree at least 3. The polynomial degree of C_G(x) is the girth of G, and the graph is Hamiltonian iff the degree equals n.

In particular, c_n gives the number of Hamiltonian cycles, so a graph is Hamiltonian iff c_n!=0. A graph is triangle-free iff c_3=0, and square-free iff c_4=0.

Since cycle counts in a disconnected graph are the sum of cycle counts in its connected components, the cycle polynomial is additive over connected components.

The following table summarizes closed forms for the cycle polynomials of some common classes of graphs.

The following table summarizes the recurrence relations for cycle polynomials for some simple classes of graphs.

The first few cycle polynomials for a number of graph families are summarized in the following table.

See also

Cycle Index, Graph Cycle, Hamiltonian Cycle, Path Polynomial

Explore with Wolfram|Alpha

Cite this as:

Weisstein, Eric W. "Cycle Polynomial." From MathWorld--A Wolfram Web Resource.

Subject classifications