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

1
vote
1answer
105 views

$q$-connectedness of random digraphs obtained from a fixed graph

Let $G = (E,V)$ be an undirected graph (which can have multiple edges or loops). Let $k,l,m\colon E\to \mathbb{R}_{\geq 0}$ be three edge-weight functions that satisfy $2k(e) + l(e) + m(e) = 1$ for ...
19
votes
0answers
331 views

Zero curves of Tutte Polynomials?

There is an extensive theory of the real and complex roots of the chromatic polynomial of a graph, a substantial fraction of this being due to the connections between the chromatic polynomial and a ...
5
votes
0answers
86 views

Determinantal formulae for Tutte polynomial

Let $G$ be a connected undirected graph. Then the number $ST(G)$ of spanning trees in $G$ equals the following specific value of the Tutte polynomial of $G$: $ST(G)=T_G(1,1)$. On the other hand, ...
7
votes
1answer
124 views

Does the Tutte polynomial of iterated cone graphs detect isomorphism?

Let $T_G(x,y)$ denote the Tutte polynomial of a graph. Of course we may have $T_G(x,y) = T_H(x,y)$ for $G$ and $H$ non-isomorphic graphs. Now let $c(G)$ denote the cone graph of $G$, i.e., the graph ...
5
votes
0answers
97 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
584 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
299 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 $\...
13
votes
2answers
483 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 \frac{...
1
vote
1answer
496 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
1k 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
375 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 $T_G(...
1
vote
1answer
161 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
564 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 ...
11
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 ...