TOPICS
Search

Cycle Polynomial

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The term cycle polynomial is used in this work for the polynomial

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

where G is a simple graph on n vertices and c_k counts its simple cycles of length k, with a graph cycle and its reversal counted once. This is analogous to the matching-generating polynomial and independence polynomial. The term "cycle polynomial" is also used for polynomials corresponding to cycle indices of permutation groups. For a graph containing a graph cycle, 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 simple graph cycle has length 3, cycle polynomials have no terms of degree less than 3. If G contains a graph cycle, 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. An acyclic graph has C_G(x)=0.

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 unoriented 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 graph path.

The following table summarizes closed forms for the cycle polynomials of some common classes of graphs. For the cycle graph, gear graph, helm graph, prism graph, sunlet graph, web graph, and Möbius ladder, the parameter satisfies n>=3. For the book graph, ladder graph, complete graph, and complete bipartite graph, n is a positive integer. For the wheel graph, n>=4. The rational functions in the table are interpreted by continuity at their removable singularities.

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 graphx^(2n)+(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(1-x)]^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(nx^4(x^(2n-2)-1))/(x^2-1)+x^n[(1-x)^n+(1+x)^n]
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 graph3x^8
44x^4+20x^6+32x^8+68x^(10)+82x^(12)+16x^(14)
522x^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.Sloane, N. J. A. Sequences A085452 and A167986 in "The On-Line Encyclopedia of Integer Sequences."

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