Does the Tutte polynomial of iterated cone graphs detect isomorphism?

Question

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 obtained from $G$ by adding a new vertex connected by an edge to every vertex of the original graph $G$. Let $c^{n}(G)$ denote the graph obtained by coning over $G$ $n$ times.

Note that we can have $T_G(x,y) = T_H(x,y)$ but $T_{c(G)}(x,y) \neq T_{c(H)}(x,y)$. For instance, take $G = K_{1,3}$ the star with three edges, and $H = P_3$ the path with three edges. Then $T_G(x,y) = T_H(x,y)$ because all trees on the same number of edges have the same Tutte polynomial, but $T_{c(G)}(x,y) \neq T_{c(H)}(x,y)$ because for instance $c(G)$ has $20$ spanning trees and $c(H)$ has $21$ spanning trees (and the number of spanning trees of any connected graph is the Tutte polynomial evaluated at $(1,1)$.)

Question: Is it the case that if $G$ and $H$ are non-isomorphic graphs then $T_{c^n(G)}(x,y) \neq T_{c^n(H)}(x,y)$ for some $n$? If so, are there some effective bounds on this $n$?

Answer 1

I don't think that's true - I think the idea from this paper works out.

Let $G$ be a simple graph and let $H$ be a spanning subgraph of $G$ having connected components of order $h_1 \geq h_2 \geq \cdots \geq h_k.$ We say that $(|E(H)|,h_1,h_2, \ldots, h_k)$ is a subgraph description of $H.$ Let now $s(G)$ be the lexicographically sorted tuple of subgraph descriptions for every subgraph of $G.$ We call $s(G)$ the subgraph sequence of $G.$

Notice that if $s(H) = s(G)$ then $s(c(H)) = s(c(G)).$

Now there are two non-isomorphic graphs having the same subgraph sequence and you can find such an example on 8 vertices in the linked paper.

But the subgraph sequence of a graph uniquely determines its Tutte polynomial so such graphs should be a counterexample.