7
$\begingroup$

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$?

$\endgroup$
  • $\begingroup$ Interesting question! $\endgroup$ – Per Alexandersson May 27 '15 at 14:30
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What does a spanning subgraph mean? I guess it is a subset of the edges that includes at least one edge adjacent to every vertex? $\endgroup$ – Sam Hopkins May 27 '15 at 21:35
  • $\begingroup$ @SamHopkins A spanning subgraph is a subgraph that contains every vertex of the original graph. $\endgroup$ – Jernej May 27 '15 at 21:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.