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

17 questions
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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
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 ...
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 ...
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 ...
335 views

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