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 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.

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

In particular, gives the number of Hamiltonian cycles, so a graph is Hamiltonian iff . A graph is triangle-free iff , and square-free iff .

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.

graph
book graph
complete bipartite graph
complete graph
cycle graph
gear graph
helm graph
ladder graph
Möbius ladder
prism graph
sunlet graph
web graph
wheel graph

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

graph	order	recurrence
antiprism graph	7
book graph	3
gear graph	4
helm graph	4
ladder graph	3
Möbius ladder	6
sunlet graph	1
web graph	6

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

graph	OEIS
antiprism graph		3
		4
		5
		6
cocktail party graph	A167986	2
		3
		4
complete graph		3
		4
		5
		6
		7
crown graph		3
		4
		5
		6
cycle graph		3
		4
		5
		6
grid graph		2
		3
		4
		5
hypercube graph	A085452	2
		3
		4
		5
-king graph		2
		3
		4
-knight graph		2
		3
		4
ladder graph		2
		3
		4
		5
		6
prism graph		3
		4
		5
		6
		7
-queen graph		2
		3
		4
-rook graph		2
		3
		4