12

There is a simple formula for the generating function of $T_{K_n}(x,y)$, which is more cleanly expressed in terms of the (equivalent) "coboundary polynomial" $X_M(q,t) = (t-1)^{r(M)} T_M(1+\frac{q}{t-1}, t)$:
$$
1+q\sum_{n \geq 1} X_{K_n}(q,t) \frac{x^n}{n!} = \left( \sum_{n \geq 0} t^{n \choose 2}\frac{x^n}{n!}\right)^q.
$$
This is essentially due to Tutte ...

10

This question is based on misunderstanding. Tutte polynomials of complete graphs are extremely easy to compute because there is a simple recurrence relation. See here for a simple to use formula. I (re)discovered this formula 20 years ago, but Ira Gessel found it much earlier. For references and background, see this paper by Gessel, and this followup by ...

8

Our program "tutte" (http://homepages.ecs.vuw.ac.nz/~djp/tutte/#download) can compute the TP of $K_{18}$ in 160s (on a recent machine with an i7).
However you wouldn't want to do it with this sort of program that works on general graphs, because the complete graph is special and by tackling it symbolically you can go much further.
I can do $K_{40}$ in ...

5

It is true. It's Exercise 11 on page 128 of "Algebraic Graph Theory", by Royle and somebody.
If I recall correctly (and I might not) the trick is to show that the number of homomorphisms determines the number of injective homomorphisms. [EDIT: as Andras notes, I should have said surjections.]
The result is quite old, and I am somewhat surprised that it's ...

3

I had already begun composing my answer when one of the authors of the paper I cite got the first post. This is as it should be, I suppose.
In any case, Haggard, Pearce, and Royle published a paper on computing Tutte polynomials in ACM Transactions on Mathematical Software Volume 37(3), article 24, 2010.
Here's the ACM link: http://dl.acm.org/citation.cfm?...

2

I think one can reduce this to computing $T_{K_n}(1,y)$.
If you consider the expansion of the Tutte polynomial in terms of subgraphs, then one may consider how this expansion breaks up under the action of permutations of the vertices of $K_n$. For a partition of $n = k_1+k_2+\cdots+k_m$, one may take a corresponding partition of the vertices of $K_n$, and ...

Only top voted, non community-wiki answers of a minimum length are eligible

#### Related Tags

co.combinatorics × 2graph-theory × 2

graph-polynomials × 2

reference-request × 1

algebraic-graph-theory × 1

tutte-polynomial × 1