TOPICS
Search

Cycle Polynomial

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

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

C_G(x)=sum_(k=3)^nc_kx^k

whose coefficients c_k give the number of simple cycles present in a graph G on n nodes. The coefficient list (c_3,c_4,...,c_p) through the graph circumference p, with zero entries retained, is the cycle length distribution sequence of Harary and Palmer (1973, p. 266).

Since the smallest possible cycle is of length 3, cycle polynomials have no terms of degree less than 3. The smallest exponent occurring in C_G(x) is the girth of G, while the polynomial degree of C_G(x) is the graph circumference. In particular, 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.

Equivalently, c_k can be obtained by counting simple paths of length k-1 whose endpoints are adjacent and dividing by k, since deleting any one of the k edges of a k-cycle leaves such a path.

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

graphC(x)
book graph S_(n+1) square P_21/2nx^4[(n-1)x^2+2]
complete bipartite graph K_(n,n)1/2sum_(k=2)^(n)(n; k)^2k!(k-1)!x^(2k)
complete graph K_n1/2sum_(k=3)^(n)(n; k)(k-1)!x^k
cycle graph C_nx^n
gear graph(n(x^(2(n+1))-x^4))/(x^2-1)
helm graphx^n+(n(x^n-x)x^2)/(x-1)
ladder graph P_2 square P_nsum_(k=1)^(n)(n-k)x^(2k+2)
=(x^4[x^(2n)+n(x^2-1)-1])/((x^2-1)^2)
Möbius ladder M_nx^(2n)-[x(x+1)]^n-[x(x-1)]^n+(n(x^(2(n+1))-x^4))/(x^2-1)
prism graph Y_n(nx^4(x^(2n-2)-1)+(x^2-1)x^n[(1-x)^n+(1+x)^n])/(x^2-1)
sunlet graph C_n circledot K_1x^n
web graph[x(x+1)]^n-[x(x-1)]^n+(n(x^(2(n+1))-x^4))/(x^2-1)
wheel graph W_nx^(n-1)+(n-1)sum_(k=3)^(n)x^k
=x^(n-1)+((n-1)x(x^2-x^n))/(x-1)

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

graphorderrecurrence
antiprism graph7p_n(x)=x^(10)p_(n-7)(x)+(3x^2+2x+2)p_(n-1)(x)-(2x^4+1)x^6p_(n-6)(x)+(x^6+2x+2)x^4p_(n-5)(x)+(3x^4-4x^3-5x^2-4x-1)x^2p_(n-4)(x)-(x^4+4x^3+7x^2+4x+1)p_(n-2)(x)-(2x^5-2x^4-4x^3-8x^2-5x-2)xp_(n-3)(x)
book graph S_(n+1) square P_23p_n(x)=p_(n-3)(x)-3p_(n-2)(x)+3p_(n-1)(x)
gear graph4p_n(x)=x^4(-p_(n-4)(x))+2(x^2+1)x^2p_(n-3)(x)+2(x^2+1)p_(n-1)(x)-(x^4+4x^2+1)p_(n-2)(x)
helm graph4p_n(x)=x^2(-p_(n-4)(x))-(x^2+4x+1)p_(n-2)(x)+2(x+1)xp_(n-3)(x)+2(x+1)p_(n-1)(x)
ladder graph P_2 square P_n3p_n(x)=x^2p_(n-3)(x)-(2x^2+1)p_(n-2)(x)+(x^2+2)p_(n-1)(x)
Möbius ladder M_n6p_n(x)=(x-1)(x+1)x^6p_(n-6)(x)-2(x^4-x-1)x^4p_(n-5)(x)+2(x^2+x+1)p_(n-1)(x)-(4x^3+5x^2+4x+1)p_(n-2)(x)+(x^6+3x^4-4x^3-4x^2-4x-1)x^2p_(n-4)(x)-2(x^5-x^4-x^3-4x^2-2x-1)xp_(n-3)(x)
sunlet graph C_n circledot K_11p_n(x)=xp_(n-1)(x)
web graph6p_n(x)=(x-1)(x+1)x^6p_(n-6)(x)-2(x^4-x-1)x^4p_(n-5)(x)+2(x^2+x+1)p_(n-1)(x)-(4x^3+5x^2+4x+1)p_(n-2)(x)+(x^6+3x^4-4x^3-4x^2-4x-1)x^2p_(n-4)(x)-2(x^5-x^4-x^3-4x^2-2x-1)xp_(n-3)(x)

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

graph G_nOEISnC_(G_n)(x)
antiprism graph38x^3+15x^4+24x^5+16x^6
48x^3+10x^4+24x^5+52x^6+56x^7+29x^8
510x^3+10x^4+12x^5+35x^6+100x^7+160x^8+140x^9+56x^(10)
612x^3+12x^4+12x^5+14x^6+48x^7+177x^8+388x^9+498x^(10)+...
cocktail party graph K_(n×2)A1679862x^4
38x^3+15x^4+24x^5+16x^6
432x^3+102x^4+288x^5+640x^6+960x^7+744x^8
complete graph K_n3x^3
44x^3+3x^4
510x^3+15x^4+12x^5
620x^3+45x^4+72x^5+60x^6
735x^3+105x^4+252x^5+420x^6+360x^7
crown graph3x^6
46x^4+16x^6+6x^8
530x^4+130x^6+270x^8+156x^(10)
690x^4+680x^6+3330x^8+7776x^(10)+4800x^(12)
cycle graph C_n3x^3
4x^4
5x^5
6x^6
grid graph P_n square P_n2x^4
34x^4+4x^6+5x^8
49x^4+12x^6+26x^8+52x^(10)+76x^(12)+32x^(14)+6x^(16)
516x^4+24x^6+61x^8+164x^(10)+446x^(12)+1100x^(14)+2102x^(16)+2436x^(18)+1874x^(20)+900x^(22)+226x^(24)
hypercube graph Q_nA0854522x^4
36x^4+16x^6+6x^8
424x^4+128x^6+696x^8+2112x^(10)+5024x^(12)+5376x^(14)+1344x^(16)
580x^4+640x^6+6720x^8+68736x^(10)+591200x^(12)+4652160x^(14)+...
(n,n)-king graph24x^3+3x^4
316x^3+29x^4+52x^5+82x^6+92x^7+61x^8+16x^9
436x^3+79x^4+176x^5+430x^6+1096x^7+2727x^8+6184x^9+12224x^(10)+20404x^(11)+27555x^(12)+...
(n,n)-knight graph2x^8
34x^4+20x^6+32x^8+68x^(10)+82x^(12)+16x^(14)
422x^4+164x^6+892x^8+3864x^(10)+13042x^(12)+27836x^(14)+37193x^(16)+30144x^(18)+13108x^(20)+2384x^(22)+120x^(24)
ladder graph P_2 square P_n2x^4
32x^4+x^6
43x^4+2x^6+x^8
54x^4+3x^6+2x^8+x^(10)
65x^4+4x^6+3x^8+2x^(10)+x^(12)
prism graph Y_n32x^3+3x^4+6x^5+3x^6
46x^4+16x^6+6x^8
55x^4+2x^5+5x^6+20x^7+5x^8+10x^9+5x^(10)
66x^4+8x^6+36x^8+36x^10+8x^(12)
77x^4+7x^6+2x^7+7x^8+42x^9+7x^(10)+70x^(11)+7x^(12)+14x^(13)+7x^(14)
(n,n)-queen graph24x^3+3x^4
336x^3+122x^4+376x^5+976x^6+1984x^7+2761x^8+1960x^9
4124x^3+776x^4+4644x^5+26414x^6+141216x^7+696906x^8+3118200x^9+12423308x^(10)+43071536x^(11)+126154214x^(12)+299319152x^(13)+539006624x^(14)+654614112x^(15)+402364270x^(16)
(n,n)-rook graph2x^4
36x^3+9x^4+36x^5+60x^6+72x^7+81x^8+48x^9
432x^3+60x^4+288x^5+1248x^6+4032x^7+11952x^8+34368x^9+91296x^(10)+211968x^(11)+417264x^(12)+670464x^(13)+822528x^(14)+678912x^(15)+284112x^(16)

See also

Cycle Index, Cycle Length Distribution Sequence, Graph Cycle, Hamiltonian Cycle, Path Polynomial

Explore with Wolfram|Alpha

References

Harary, F. and Palmer, E. M. "A Survey of Graphical Enumeration Problems." In A Survey of Combinatorial Theory (Ed. J. N. Srivastava). Amsterdam, Netherlands: North-Holland, pp. 259-275, 1973.

Referenced on Wolfram|Alpha

Cycle Polynomial

Cite this as:

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

Subject classifications