Task list filter?

Choose required ranks and required tasks. The table of contents will list only tasks having one of the required ranks in corresponding rankings and at least one of the required tags (overall). If you wish to filter only according to some rankings or tags, leave the other groups empty.

Task rankings

Difficulty level

Task tags

Task type
«
«
«

Tutte polynomial of a cycle

Task number: 4067

Determine the Tutte polynomial for the cycle of length k.

  • Hint

    Use the recurrence for the Tutte polynomial TG(x,y).

    TG={xTGewhen e is a bridge,yTGewhen e is a loop, TGe+TG/ewhen e is not a bridge nor a loop.

    Furthermore, an edgeless graph has TG=1.

  • Solution

    In the first step, the last option is used. So TCk=TPk1+TCk1.

    By removing leaves, we find that TPk1=xk1, which leads to the recurrence TCk=xk1+TCk1

    Lastly, we apply recurrence to the bigon, i.e. to two vertices connected by two edges. Then one vertex is left with a loop C1, where TC1=y.

  • Answer

    The Tutte polynomial of a cycle is: TCk(x,y)=xk1+xk2++x2+x+y.

Difficulty level: Easy task (using definitions and simple reasoning)
Routine calculation training
Cs translation
Send comment on task by email