Questions about the Tutte polynomial of graphs and matroids, which is a polynomial in two variables encoding many interesting combinatorial informations.

learn more… | top users | synonyms

5
votes
0answers
84 views

Implementations of Tutte polynomial [reference request, of a kind]

This question is not a 100% fit for MO, but it is a serious question that can be viewed as a sort of reference request, and I think fits here more than elsewhere. I have been asked to write a chapter ...
12
votes
1answer
480 views

Tutte polynomials, graph complements and degree sequences

Harary and Akiyama asked whether there exists a non self-complementary (SC) graph $G$ having the same chromatic polynomial as its complement. It was later shown that there indeed exist such graphs ...
12
votes
0answers
249 views

Are the zeros of Tutte polynomials dense in $\mathbb C^2$?

For the chromatic polynomials of graphs we have two nice theorems which describe the behavior of their zeros: Thomassen proved that the set of real zeros of all chromatic polynomials is the union of ...
9
votes
0answers
238 views

Generating functions, Tutte polynomials, and the bivariate series $\sum_n x^n y^{n^2} / n!$.

A few years ago I computed the Tutte polynomials of the matroids given by the classical Coxeter groups, and found that their generating functions are all simple variations of the series $\sum_n ...
1
vote
1answer
288 views

Number of spanning subgraphs of $K_n$ with given number of edges and connected components

Given some positive integers $n,e$ and $c$, I would like to know the number of spanning subgraphs of $K_n$ having $e$ edges and $c$ connected components. Essentially, what I am asking for here is ...
9
votes
5answers
991 views

How many Tutte polynomials of complete graphs are known?

I would like to compute the Tutte polynomial of the complete graph $K_n$ for n as large as possible. Using a program by Björklund, Husfeldt, Kaski, Koivisto (here), I managed to compute up to n=18 on ...
6
votes
3answers
344 views

Tutte polynomials of appropriate Cayley graphs

I was quite intrigued by Tutte polynomials in a recent talk I had been to. It was introduced as a polynomial associated to a undirected finite graph. For a graph $G=(V,E)$ we form the polynomial ...
1
vote
1answer
143 views

The Tutte Polynomial - is a `crossing' the same as a `bridge'?

Hey guys, The following paper uses the term `bridge' in their definition of the Tutte polynomial: Bennett Thompson, David J. Pearce, Craig Anslow, and Gary Haggard. Visualizing the computation tree ...
8
votes
2answers
506 views

Derivative of Tutte polynomial at -1

Let Tutte polynomial on graph with edge-set $E$ be defined as follows $$f(q,v)=\sum_{A\subseteq E} q^{\kappa(A)} v^{|A|}$$ Here the sum is over all subgraphs $A$, $\kappa(A)$ is the number of ...
10
votes
9answers
2k views

What is the Tutte polynomial encoding?

Pretty much exactly what it says on the tin. Let G be a connected graph; then the Tutte polynomial T_G(x,y) carries a lot of information about G. However, it obviously doesn't encode everything about ...