**5**

votes

**0**answers

71 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

**1**answer

119 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

**0**answers

90 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

**1**answer

546 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

**0**answers

263 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

**2**answers

469 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

**1**answer

378 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

**5**answers

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

**3**answers

362 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

**1**answer

155 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

**2**answers

541 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

**9**answers

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 ...