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 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 give the number of simple cycles present in a graph on nodes.
The following table summarizes closed forms for the cycle polynomials of some common classes of graphs.
|complete bipartite graph
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.