# Questions tagged [tutte-polynomial]

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

**2**

votes

**0**answers

68 views

### Tutte polynomial from independent sets of a graph

Let $G$ be a connected graph with chromatic polynomial $X(G,q)$. Since $k$-proper coloring a graph is same as partitioning the vertex set $V$ into $k$ independent sets (a subset of the vertex set in ...

**0**

votes

**0**answers

111 views

### Why are two rank 2 matroids isomorphic

Assume we have two matroids $M_1$ and $M_2$ in rank 2, which have equal grounds sets. If both matroids have the same amount of parallel classes $k$ and\
or loops $l$ (but placed in different placed of ...

**3**

votes

**1**answer

171 views

### Non-isomorphic matroids with the same Tutte Polynomial

Im currently reading Matroids: a geometric introduction by Gordon and McNulty. Chapter 9 talks about Tutte polynomials.
My question is this Suppose we have two matroids M1 and M2. Both matroids have ...

**1**

vote

**1**answer

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

**21**

votes

**0**answers

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

**7**

votes

**0**answers

138 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

142 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

107 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

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

**13**

votes

**0**answers

335 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

541 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

**1**answer

801 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

2k 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

397 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

**2**answers

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

**10**

votes

**2**answers

680 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

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