2
$\begingroup$

You can turn any graph $G$ (except those with isolated points) into a trivalent one $G'$, even with an unique result, by doing the following transformation of each $n-$degree vertex into a loop (I stopped at degree $n=4$ since it is obvious):

enter image description here

(The third row already shows this can't be 1:1, but nevermind.) I'm fairly sure somebody had the idea before. What graph properties stay invariant? Especially, assume you declare a fudge factor $f_n$ to be multiplied onto a graph polynomial when replacing a node with degree $n$. Can you choose special parameters $x,y$ of the Tutte polynomial $T(x,y)$ so it stays invariant, $T(G')=f_n*T(G)$, preferrably even if the transformation is done stepwise? ($f_n$ here must be the same for any node with degree $n$, but the value of $f_n$ may be some function of the parameters $x,y$ of the Tutte polynomial.) The deletion–contraction recurrence should help...

$\endgroup$

1 Answer 1

2
$\begingroup$

The process of replacing a vertex of degree $d > 3$ with a $d$-cycle is normally called truncating a vertex (from the idea of slicing off a corner of a geometric shape).

If the original graph is planar, then there is one obvious way to connect up the $d$-vertices in a cycle, and so there would be a flicker of hope that some graph parameters might behave nicely.

But if you permit the new $d$-cycle to be formed in any arbitrary fashion, then there's no chance of controlling the Tutte polynomial.

To find an explicit counterexample, I just took the smallest graph that I could find with a single vertex of degree $4$ and the rest of degree at least $3$, which is the wheel on 5 vertices.

There are two ways to truncate this single vertex, one of which yields the cube, also known as the planar cubic ladder, and the other giving a different $3$-regular graph on $8$ vertices called the cubic Möbius ladder.

These two graphs do not have the same Tutte polynomial, in fact they do not even have the same number of spanning trees.

$\endgroup$
1
  • $\begingroup$ Too bad, I thought since this all makes vaguely sense when seen as juggling with the Casimirs of a Lie algebra, there could have come more out of it. <shrug> $\endgroup$ Commented Dec 6, 2021 at 11:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .